Теория и реализация языков программирования




Контекстно-свободные грамматики и автоматы с магазинной памятью - часть 3


у которого функция переходов D содержит элементы:

D(q0, a, Z) = {(q0, aZ)}, D(q0, b, Z) = {(q0, bZ)}, D(q0, a, a) = {(q0, aa), {q1, e)}, D(q0, a, b) = {(q0, ab)}, D(q0, b, a) = {(q0, ba)}, D(q0, b, b) = {(q0, bb), (q1, e)}, D(q1, a, a) = {(q1, e)}, D(q1, b, b) = {(q1, e)}, D(q1, e, Z) = {(q2, e)}.

Нетрудно показать, что

L(M) = \{ww^R \! | \! w \; \in \; \{a, b\}^+\}
, где wR обозначает обращение ("переворачивание") цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если

(q_0, w, Z_0) \vdash^* (q, e, e)
для некоторого
q \in Q
. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива




Содержание  Назад  Вперед