Question

Which of the following correctly resembles the given state diagram?

(a) {ww^r|w=(a+b)*}

(b) ε is called the initial stack symbol

(c) Both (a) and (b)

(d) None of the mentioned

I have been asked this question at a job interview.

Origin of the question is From PDA to Grammars in chapter Push Down Automata of Automata Theory

Answer 1

Right option is (a) {ww^r|w=(a+b)*}

For explanation: Initially we put a special symbol ‘#’ into the empty stack. At state q1, the w is being read. In state q2, each 0 or 1 is popped when it matches the input. If any other input is given, the PDA will go to a dead state. When we reach that special symbol ‘#’, we go to the accepting state q3.