Может ли каждое состояние быть конечным при построении детерминированных автоматов с выталкиванием вниз?
У меня возникли проблемы, в частности, с созданием 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, ε)}