Example 2.2.6.
Consider L = 0*1* _ {1m0n1n | m1, n0}. L cannot be proven non-regular by means of the pumping lemma the first letter of any string in L can be pumped any number of times.
However, L can be proven non-regular by mapping it to a known non-regular language.
Step 1: Let L1 = L _ 1+0*1* = {1m0n1n | m1, n0} and L1 is regular if L is.
Step 2: Let L2 = 1+0\L1 = {0n-11n | n1} and L2 is regular if L1 is.
Step 3: Let L3 = {_} _ {0}L2 = {0n1n | n0} and L3 is regular if L2 is. But L3 is not regular, and hence L cannot be regular.
| Previous slide | Next slide | Back to first slide | View graphic version |