Why the following language cannot be defined using a Pushdown Automata (PDA)?

1.6k views Asked by At

{0 i1 j2 k | 0 <= i <= j <= k }

Is it possible to design a PDA for this language?

I think the answer is no, and it can only be defined using at least a context free grammar.

However, I don't know why. I need some discussion and explanation regarding this.

1

There are 1 answers

0
Hassan Abbasi On

The answer is no. Actually there are neither a CFG nor an NPDA for this language. The proof can be established using a pumping lemma for context free languages.