Всъщност е доста просто. Всеки път, когато прочетете "ab", вие съхранявате токен в стека. След това, след като прочетете "c", взимате едно от този жетон. След това за всяко "bb" взимате по един жетон от стека. Когато стекът е празен, приемате.
За самия NPDA зависи как дефинирате приемането. От въпроса ви не разбирам какво имате предвид под „написване на a, след което движение надясно“. Бъркате ли NPDA с машина на Тюринг? NPDA е много подобен на NFA (недетерминирани крайни автомати), с изключение на това, че е оборудван със стек, в който можете да поставите символи на стека. Прочетете повече тук: http://www.cs.duke.edu/~rodger/courses/cps140/lects/sectnpdaH.pdf
По-долу е таблицата на прехода, като се приемат символи на стека {A,Z}, където Z е началният символ на стека. Приемам, когато сме в единственото приемащо състояние qa и сме приключили с четенето на входната лента. Да приемем, че всеки преход винаги консумира един стеков символ и ако няма повече символ за консумиране, докато NPDA не е в състояние на приемане, NPDA не приема (или отхвърля) низа.
В таблицата по-долу първата колона представлява състоянието, в което се намираме в момента, и символа на стека, който четем. Следващите колони представляват новото състояние и символ на стека, изтласкан към стека при четене на конкретен знак във входния низ (или непрочитане на никакъв знак с ε)
+------++---------+-------+--------+-------+
| || a | b | c | ε |
+------++---------+-------+--------+-------+
|(q1,Z)|| (q2,Z) | - | - | - |
+------++---------+-------+--------+-------+
|(q1,A)|| (q2,A) | - | (q3,ε) | - |
+------++---------+-------+--------+-------+
|(q2,Z)|| - |(q1,ZA) | - | - |
+------++---------+-------+--------+-------+
|(q2,A)|| - |(q1,AA) | - | - |
+------++---------+-------+--------+-------+
|(q3,Z)|| - | - | - |(qa,ε) |
+------++---------+-------+--------+-------+
|(q3,A)|| - | (q4,A) | - | - |
+------++---------+-------+--------+-------+
|(q4,A)|| - | (q3,ε) | - | - |
+------++---------+-------+--------+-------+
Ключовата идея тук е, че числото A в стека представлява колко пъти фразата "ab" се появява във входния низ.
Можете да видите, че при четене на "a" в състояние q1 със символ на стека Z, ние връщаме Z обратно в стека. Което означава, че все още не е открит "ab". След това ще премине към q2.
В q2 приемаме само "b", всеки друг вход ще доведе до увисване (и следователно отхвърляне). Той изтласква обратно състоянието, което е прочел, в стека, плюс допълнително A, което ефективно увеличава броя на A в стека с 1, тъй като този преход представлява допълнителна фраза "ab" във входния низ.
Състоянието q3 представлява частта след успешно прочитане на "c". Имайте предвид, че преходът от q1 към q3 трябва да консумира A, а не Z, тъй като имаме ограничението n >= 1. След това, при прочитане на „b“, ще премине в състояние q4, за да изчака друго „b“. По-късно q4, при прочитане на "b", ще консумира символа стек A, съвпадащ
В състояние q3 ние също искаме преход към състояние на приемане qa, след като достигнем символа на стека Z, отнасяйки се до състоянието, в което има n копия на "ab" и n-1 копия на "bb".
Състояние q4 приема само входния низ "b" със символ на стека A, представляващ намирането на нова фраза "bb", която трябва да съответства на една фраза "ab", намерена преди това.
Надявам се това да помогне!
person
justhalf
schedule
28.11.2013
