Come costruire un pushdown automi per L= { w ∈ {a, b}* | w non è uguale xx^R per qualche x ∈ {a, b}* }
0
Sto supponendo che si desidera un non-deterministico push-down automa. Non credo che questo è fattibile con un deterministico PDA.
Questo suona come un compito, quindi sto solo andando a dare un quadro generale:
È essenzialmente indovinare dove il centro della stringa. A spingere gli elementi nello stack, fino a un certo punto si indovina che hai raggiunto il centro della corda. Si avvia quindi a confronto il vostro ingresso per gli elementi che si sta popping fuori stack. Non si riesce se non corrispondono. Si riesce, se si raggiunge la fine dell'input esattamente come la pila è vuota.