Context Free Grammar

Question

Is 0^n 1^n 0^n 1^n where n>=0 a CFG ?

Its given that its not CFG , please explain how ?

Comments

We can't keep track of exact number of 0's pushed into stack when it comes to second 0, and here PDA fails. hence not a CFG.

Where as for a^m b^n c^n d^m, which is a CFG.

1) (For a) push 'm' times => 2) (for b) push 'n' times => 3) (for c) pop 'n' times => 4) (for d) pop 'm' times

Answer 1

We use the pumping lemma whenever we want to prove that something is not a CFG.

Pumping lemma states: If it is a CFG, then it can be pumped.

Use the contrapositive of that statement, i.e., if it can't be pumped, then it is NOT a CFG.

Watch this video if you want a good explanation of pumping lemma for CFG's.