Push Down Automanton-Computation

Я пытаюсь понять, как работает КПК. На следующей диаграмме я понимаю, как работают функции перехода и как должен обновляться стек. Но единственный вопрос, который у меня есть, это почему состояние Start также является состоянием принятия? в то время как КПК для L = {on1n | n ≥ 0} означает, что он не должен принимать пустую строку. Может кто-нибудь объяснить причину, по которой начало принимать состояние, пожалуйста?

введите здесь описание изображения


person Lucy    schedule 09.04.2014    source источник


Ответы (2)


L = {0n1n | п ≥ 0}

Когда n=0, строка:

0010 = ноль 0, за которым следуют ноль 1, что является пустой строкой. Итак, согласно определению, язык L включает пустую строку.

Если бы он не принимал пустую строку, определение было бы таким:

L = {0n1n | п > 0}

person uba    schedule 11.04.2014

Поскольку NFA принимает пустые строки

person Joshua Swain    schedule 02.06.2018