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

In the given question, we have 2 languages L1 and L2. We need to find,the language is regular or not .And if the language is not regular we need to check it is CFL or not.

Solution: We can't construct DFA or NFA for a non regular language. Since,finite automata do not have auxiliary memory ,it can not be constructed for languages where memory is required Here,in L1 we need i = j or j=k (number of 0 is equal to number of 1 or number of 1 is equal to number of 0).Since we can't store number of times 0s,1s or 2s have appeared in any string present in language L1, it is impossible to compare the number of 0s with 1s or 1s with 2s.Thus ,the language L1 is not regular.Moreover , construction of DFA or NFA for language L1 is not possible .Hence it can be said that the language L1 is not regualr.

The langue L1 can be constructed using a single stack. Since in L1 we need i=j or j=k,we can use a single stack for developing the language. Let us take an example of string in language L1. String S1=00112(i = j) or S2= 01122 ( j = k).

Now, if we scan string S1 from left to write and push all 0s into the stack .

After the 0s are pushed into the stack , we perform pop aperation for each 1 we encounter.

If the stack is empty as we encounter the last 1 in the scanning of string it means that the number of 0s in the given string is equal to number of 1s.

Now ,we can simply scan 2s and reach to the end of string as there are no condition attach to the number of 2s in the given string . The image below shows ,how push and pop operation can be performed using string S1.

Similar operation can be performed to contruct string S2 .

Thus , we can construct strings in L1 with single stack. And if a language can be constructed using a single stack than it is CFL.

So, Language L1 is not regular but it is CFL.

Language L2 is regualr. Language L2 includes all strings where 1,2 and 3 are in order 123 and has nothing to do with the numbers of 1s ,2s and 3s. Here , we can easily construct DFA and NFA for language L2. Since DFA and NFA can be constructed only for regular language,it can be said that language L2 is regualr. The image below shows NFA and DFA for language L2.

So in the given question ,L1 is CFL and L2 is regular