Как разработать NPDA для принятия этих языков? - PullRequest
Новая
       20

Как разработать NPDA для принятия этих языков?

2 голосов
/ 03 февраля 2020

Я хочу спроектировать NPDA (недетерминированные автоматы нажатия), который поддерживает два языка. Пожалуйста, объясните, как их проектировать. 

L(r) where r = abb*aba*
L(r) = {a^nb^2n : n > 0}

1 Ответ

2 голосов
/ 03 февраля 2020

Первый из них может работать следующим образом:

  1. читает a в первом состоянии и помещает pu sh a в стек; переход в новое состояние
  2. , чтение ab во втором состоянии и pu sh ab в стек; переход в новое состояние
  3. навсегда читает b в третьем состоянии, каждый раз помещая b в стек. если вы в конце концов прочитаете a, перейдите в новое состояние и pu sh a a в стеке
  4. прочитаете b в четвертом состоянии, поместив b в стек; переход в новое состояние
  5. чтение a в пятом состоянии навсегда, помещая a в стек; в любой момент недетерминированный переход в новое состояние
  6. в шестом состоянии, просто ничего не читать и вываливать вещи из стека. это состояние принимает, и npda принимает входную строку, если вход полностью прочитан и стек пуст.

Второй может работать так:

  1. прочитайте хотя бы один a и pu sh его в стеке, затем перейдите в новое состояние
  2. продолжайте чтение навсегда во втором состоянии, каждый раз помещая один a в стек; если вы видите b, go в новое состояние
  3. прочитайте b в третьем состоянии и вытолкните a из стека; go в новое состояние
  4. прочитайте b в четвертом состоянии и оставьте стек в покое; go вернуться в третье состояние
  5. продолжать читать b в третьем и четвертом состояниях, пока не закончится ввод; если вы находитесь в четвертом состоянии, у вас закончился ввод и у вас пустой стек, тогда и только тогда кпк принимает входную строку

EDIT: схема необходимых переходов.

Первый: 

q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, b, a) -> (q2, ba)
(q2, b, b) -> (q2, bb)
(q2, a, b) -> (q3, ab)
(q3, b, a) -> (q4, ba)
(q4, a, b) -> (q4, ab)
(q4, a, a) -> (q4, aa)
(q4, e, a) -> (q5, a)
(q4, e, b) -> (q5, b)
q5 is accepting

Второй: 

q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, a, a) -> (q1, aa)
(q1, b, a) -> (q2, a)
(q2, b, a) -> (q3, e)
(q3, b, a) -> (q2, a)
q3 is accepting

Оба NPDA предназначены для принятия в состоянии принятия, когда стек пуст и вход исчерпан.

...