Question

Consider the two languages below:

L1 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0 and i = j or j = k}

L2 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0}

One of the languages in the above problem is regular. Which one? Prove it.

Prove that the OTHER one is not regular.

Is the non-regular one context free? Prove it.

Answer 1

1.

L1 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0 and i = j or j = k}

L2 = {w | w є {0,1,2}* and is of the form 0i1j2k where i, j and k ≥ 0}

Among the above L2 is regular the reason is as follows,

L2 says that it comprises all the values of the form 0i1j2k and the restriction on i,j,k is i≥ 0,j≥ 0 and k≥ 0. So acceptable language is,

L2 = { 0*1*2* } says that any number of 0’s , any number of 1’s and any number of 2’s.

One can design a NFA for this type of language. A language which can be solved in DFA/NFA is finite and is Regular.

On the other hand, L1 says that it comprises all the values of the form 0i1j2k and the restriction on i,j,k is along with i≥ 0,j≥ 0 and k≥ 0. there is a comparison given i = j or j = k. So the acceptable language is,

L1 = { 0i1i2* U 0*1j2j }

The DFA / NFA don't have a memory to store and compare so the given L1 cannot be solved by the DFA / NFA also. So L1 is a non-regular language.

2. Is the non-regular one context free? Prove it.

By the above figure we can say that Regular language is a subset of Context Free language. Context Free language is the subset of Context Sensitive Language. Context Sensitive language is the subset of Recursive Language.

A non-regular language might be any of the CFL,CSL,Rec. So the non-regular one need not be necessarily context free but yes it can be possible.