Могат ли всички състояния да бъдат окончателни в детерминистичен Pushdown автомат?

Когато конструирате детерминистични автомати за натискане, всяко състояние може ли да бъде крайно състояние?

Имам проблем по-конкретно с конструирането на 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, ε) }


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


Отговори (1)


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

person difql    schedule 12.09.2014