Описание работы магазинного преобразователя
Для описания работы магазинного преобразователя необходимо дать его определение.
| Определение:
Мп={P, S, s0, H, h0, F, W, q}, где P - входной алфавит, состоящий из символов, записываемых на входную ленту; W - выходной алфавит, содержащий символы, записываемые на выходную ленту; H - магазинный алфавит, содержащий символы, записываемые и считываемые из магазина; h0 - маркер дна магазина, он принадлежит H; S - множество состояний преобразователя; s0- начальное состояние из множества S; F - множество конечных состояний, представляющих собой подмножество S; j - функция переходов преобразователя, которая задает отображение,
x H Ю S x H* x W* . Она может быть записана в функциональном виде:
О H, p О P, b О H*, e О W* и s,s' О S. |
Определим конфигурацию Мп как четверку
- (s, ac, rh, d),
где ac
О P*, rh
О H*
и d
О W*.
Если такту работы преобразователя соответствует конфигурация (s, ac, rh , d) и определена функция переходов j(s, a, h) = (s', b, e), то происходит смена конфигурации, которую условимся записывать так:
- (s, ac,
rh, d) |-- (s', c, rb,
de).
Последовательность сменяющих друг друга конфигураций, как обычно, обозначим символом |--*. В качестве начальной примем конфигурацию, которой соответствует заданная входная цепочка c
на ленте, цепочка h0I в магазине, начальное состояние s0
и пустая цепочка на выходной ленте:
(s0, c, h0I, $).
Конечной или заключительной конфигурацией назовем четверку (sk, $, $, d), где sk
- одно из заключительных состояний из множества F, а d
- выходная цепочка.
Пред.СтраницаСлед.Страница
