Могут ли все состояния быть окончательными в детерминированных автоматах с выталкиванием?

Может ли каждое состояние быть конечным при построении детерминированных автоматов с выталкиванием вниз?

У меня возникли проблемы, в частности, с созданием DPDA, который принимает следующий язык:

L = { 0n 1m | п ≥ м}

Мой подход состоит в том, чтобы сделать начальное состояние конечным состоянием, которое может помещать 0 в стек для ввода 0, а затем переходить в другое конечное состояние, которое может выталкивать 0 из стека для ввода 1. Я считаю, что это решение правильное, но кажется необычным, что каждое состояние является конечным состоянием, и я хочу убедиться, что мой подход действителен.

Это правильный подход? Могу ли я иметь оба состояния в качестве конечных состояний? Вот точная функция перехода δ для моего DPDA.

δ(q0, 0, Z0) = { (q0, 0 Z0)}

δ(q0, 0, 0) = {(q0, 0 0)}

δ(q0, 1, 0) = {(q1, ε)}

δ(q1, 1, 0) = {(q1, ε)}


person Luke Godfrey    schedule 21.04.2014    source источник


Ответы (1)


Конечно, каждое состояние может быть окончательным в детерминированном автомате выталкивания вниз. Ваш подход мне кажется правильным. В зависимости от вашего определения детерминизма может потребоваться также добавить переход, который имеет дело со случаем, когда вы читаете 0 в состоянии q_1, чтобы иметь общую функцию перехода (но это зависит от того, какой детерминизм в вашем контексте определяется как .)

person difql    schedule 12.09.2014