The Gateway to Computer Science Excellence
0 votes
Is 0^n 1^n 0^n 1^n where n>=0 a CFG ?

Its given that its not CFG , please explain how ?
in Theory of Computation by (285 points) | 35 views
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

1 Answer

0 votes

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.

by Active (1.1k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,596 answers
102,078 users