Search code examples
context-free-grammarpumping-lemma

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

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?

Solution

  • 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