Contextfree language or not? I can write a grammar but not use pumping lemma

Question

I have the language: L = {0^i 1^i | i >= 0}

The grammar that describes it proves it is a context free language: S -> 0S1 | e

If a language is context free, Pumping Lemma should hold. I can however not get it to work, no matter what i choose to "pump", i will get a mix of 0's and 1's, e.g. 0101.

Am i correct that it is really a context free language? If so, can you give an example of using Pumping Lemma?

For CF languages, you choose two strings to "pump" (express a string in the language as uvxyz, then pump both v and y). So it should be trivial to choose v and y to meet the conditions of the CF pumping lemma and make the proof work in this example. (Hint: x will be the null string.) — Jim Lewis
Also, you should be aware that, although you can use the CFPL to prove a language is not context free, the proof does not work in the other direction. — Jim Lewis
I have s = uvxyz, can you show how you want to split a string in L so it can be pumped? Even if i choose v or y to be empty, not both of them can be, and i will eventually pump something up. I can choose too pump only 0's, getting more 0's than 1's - only 1's, getting more 1's than 0's - both 0's and 1's getting me ...0101... when pumping. — Kent Munthe Caspersen
have you tried v='0', x=e, y='1'? v and y are 'pumped' an equal number of times if you're using CFPL. — Jim Lewis
@KentMuntheCaspersen (1) These lemmas can be used to determine if a particular language is not in a given language class. However, they cannot be used to determine if a language is in a given class , since satisfying the pumping lemma is a necessary, but not sufficient, condition for class membership. Link (2) Read: Pumping lemma for CFG doubt — Grijesh Chauhan

Garrison Garrison · Accepted Answer · 2013-11-18T06:12:41

If you can describe a language with a context free grammar, then the language is context free. It would be difficult to prove a language is context free using the pumping lemma, because even if you find a string that can be pumped, there still might be a string that cannot be pumped.

You usually use the pumping lemma to prove a language is not context free. Because all you need is one example of a string that cannot be pumped.

Here is an example of a string in L = {0^i 1^i | i >= 0} and how it can be pumped.

string w=01, can be split as follows:

u = empty   
v = 0  
x = empty  
y = 1   
z = empty

u v^i x y^i z is in L for every i >= 0

Contextfree language or not? I can write a grammar but not use pumping lemma

1 Answers