Como construir um pushdown automata para L= { w ∈ {a, b}* | w não é igual a xx^R, para algum x ∈ {a, b}* }
0
Eu estou supondo que você quer um não-determinístico push-down autômato. Eu não acho que isso é factível com um determinista PDA.
Isso soa como uma lição de problema, então, eu só vou dar uma descrição geral:
Essencialmente, você adivinhar onde está o centro da seqüência de caracteres. Você empurrar elementos na pilha, até que em algum momento você acho que você já atingiu o centro da seqüência de caracteres. Você, em seguida, começar a comparar a sua entrada para os elementos que você está popping fora a pilha. Você falhar se eles não corresponderem. Você terá êxito se você chegar ao final da entrada exatamente como a pilha está vazia.