Когато конструирате детерминистични автомати за натискане, всяко състояние може ли да бъде крайно състояние?
Имам проблем по-конкретно с конструирането на DPDA, който приема следния език:
L = { 0n 1m | n ≥ m }
Моят подход е да направя първоначалното състояние крайно състояние, което може да изтласка 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, ε) }