Cum de a construi o automatelor pushdown pentru L= { w ∈ {a, b}* | w nu este egal xx^R pentru un x ∈ {a, b}* }
0
Presupun că vrei un non-deterministe push-down automat. Nu cred că acest lucru este greu de realizat cu un determinist PDA.
Aceasta pare a fi o problemă teme, așa că eu sunt doar de gând să dau o descriere generală:
În esență, ghici în cazul în care centrul de șir este. Te împinge elemente pe stiva, până când, la un moment dat să cred că ai ajuns la centrul de șir. Atunci începem să ne comparăm dvs. de intrare pentru elemente pe care le tragi de pe stivă. Vei eșua dacă nu se potrivesc. Veți reuși dacă ajunge la sfârșitul de intrare exact ca stiva este goală.