1
$\begingroup$

Using non-determinism to create a PDA to recognize non-palindromes is easy.enter image description here

My first instinct was to say yes, but it would be extremely complicated. After thinking about it, I don't think you could.

$\endgroup$
1
$\begingroup$

The language of palindromes isn't DCFL, see for example this question, which proves this for the closely related language of even length palindromes. Since DCFL are closed under complementation, it follows that your language is not DCFL.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.