Является ли Pushdown-автомат с переходом Epsilon NDPA?

Предположим, у нас есть этот PA:

-> q0 (e, e -> $) --> q1

Где:

q0 — конечное и начальное состояние; e это эпсилон (пусто); и q1 — другое состояние.

Если бы автомат прочитал слово e, он мог бы либо совершить переход к q1, либо остановиться на q0.

Итак, будет ли этот PA недетерминированным?

Мой учитель говорит, что этого не произойдет, потому что в действительности автомат может следовать только по одному пути: поскольку слово пусто и все символы уже использованы в q0, он не совершит никакого перехода; однако мы не уверены, прав ли он (кстати, он говорит, что для того, чтобы PA распознал слово, оно должно быть не только в конечном состоянии, но и все символы слова должны быть израсходованы).


automata pushdown-automaton
person andre_ss6    schedule 07.10.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Чтобы PA был детерминированным, он должен следовать как минимум следующему правилу:

Если существует эпсилон-переход из состояния q, не должно быть никакого алфавитного перехода из этого состояния.

Итак, в вашем случае, если нет другого правила, PA является детерминированным.

person abbaasi    schedule 12.10.2015
comment
Даже в таком случае я указал? Заметим, что состояние q0 является не только начальным, но и конечным состоянием. - person andre_ss6; 13.10.2015