Question

Which of the following can be accepted by a DPDA?

(a) The set of even length palindrome over {a,b}

(b) The set of odd length palindrome over {a,b}

(c) {xx^c| where c stands for the complement,{0,1}}

(d) None of the mentioned

The question was posed to me during an interview.

My enquiry is from From Grammars to Push Down Automata in section Push Down Automata of Automata Theory

Answer 1

Right answer is (d) None of the mentioned

Explanation: Theorem: The language pal of palindromes over the alphabet {0,1} cannot be accepted by any finite automaton , and it is therefore not regular.