Ako sa postaviť pushdown automaty pre L= { w ∈ {a, b}* | w sa nerovná xx^R pre niektoré x ∈ {a, b}* }?

Ja som za predpokladu, že chcete non-deterministický push-down automat. Nemyslím si, že to je realizovateľný s deterministický PDA.

To znie ako domáca úloha, problém, tak ja som len chcel dať všeobecný prehľad:

Ste v podstate hádajte, kde center reťazca je. Budete tlačiť prvkami na zásobník, až v určitom okamihu si myslím, že ste dosiahli centre reťazec. Potom môžete začať porovnávanie vstup na prvky, ktoré budete objavovať mimo zásobníka. Môžete zlyhať, ak sa nezhodujú. Ak sa vám podarí sa vám dostať sa na koniec textu presne tak, ako zásobník je prázdny.