Question

Let L be the language {0ⁿ 1^m : n ≤ m ≤ 2n}. Is L regular? contextfree but not regular? or not context-free? Show that your answer is correct.

Answer 1

pumping lemma for regular languages:

1)assume given language is regular and there exist a finite automata with 2k states.

2)take a valid string z from L.

z=00111

3)divide the string z into 3 parts,U,V,W in such a way that |V|>=1 and |UV|<=2k

U=0

V=0

W=111

4)if for any value of i, UV^IW belongs to L then L is regular otherwise L is not regular.

say i=3 then UVⁱW becomes 0000111  this is not belongs to L

this is contradiction to given statement.

therefore L is not regular.

The given language is context free because we can able to write context free grammar for this:

cfg is

S-.>0S11 | A

A->0A1 | ϵ