Question

Which of the following assertion is false?

(a) If L is a language accepted by PDA1 by final state, there exist a PDA2 that accepts L by empty stack i.e. L=L(PDA1)=L(PDA2)

(b) If L is a CFL then there exists a push down automata P accepting CF; ; by empty stack i.e. L=M(P)

(c) Let L is a language accepted by PDA1 then there exist a CFG X such that L(X)=M(P)

(d) All of the mentioned

The question was posed to me during a job interview.

This intriguing question originated from From PDA to Grammars topic in portion Push Down Automata of Automata Theory

Answer 1

Right option is (d) All of the mentioned

To explain: All the assertions mentioned are theorems or corollary.