search
Log In
0 votes
44 views
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 44 views
0
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.

Related questions

0 votes
1 answer
1
51 views
L=0^i 1^j 2^k | i=j or j=k is the grammar DCFG?
asked Oct 23, 2018 in Theory of Computation aditi19 51 views
0 votes
0 answers
2
105 views
Consider the following CFG 'G' S--> aA/bSS/SS A--> aAb/bAa/AA/ε The language generated by G is: a)Set of all strings with atleast one 'a' b)Set of all strings with atleast two a's c)Set of all strings with atleast one more 'a' than number of b's d)None of these
asked Oct 18, 2018 in Theory of Computation Sambhrant Maurya 105 views
0 votes
0 answers
3
91 views asked Sep 5, 2018 in Theory of Computation Deepalitrapti 91 views
0 votes
1 answer
4
54 views
What is Non-Inheritant grammar and inheritant Grammar? Please explain with an example.
asked May 14, 2018 in Theory of Computation SreenivasaRaju 54 views
...