+1 vote
64 views

Consider the following languages:

$L_{1}= \big\{0^{n+m} \ 1^{k+l}\ | \ m=l, m,n,k,l \geq 1 \big\}$

$L_{2}= \big\{0^{n} \big(1^ {2}\big)^{m}\ | \ m,n\geq 0 \big\}$

Which of the following is true?

1. $L_{1}$ is regular but not $L_{2}$
2. $L_{2}$ is regular but not $L_{1}$
3. $L_{1}$ and $L_{2}$ are not-regular
4. $L_{1}$ and $L_{2}$ are regular

Is L1 regular ?

edited ago | 64 views

I think L1 reduces to {0n0m1m1k}, therefore Context Free. Is it ?

Update: Snce n,k>=1, therefore, n and k can cover up the m of 0 and 1 respectively, so L1 becomes {0n1k}, which is regular.

both are reg lang
both Are Regular, considering L1, the minimum length of string is 0011,

Now for each and every case you can put m = l = 1, and thus make it regular. Now with the help of n and k, scaling them as much as you can, independently.

And L2 = {0*(11)*} which is also regular.

L2 is clearly regular as it can be written as : 0* (11)* in regular expression form..

Given L1 :  0n+m 1k+l  |  m = l and m,n,k,l >= 1

Now the key thing here is to satisfy m = l , we can adjust n and k accordingly , thereby the given language reduces to :

L1 :  01y  |  x,y >= 2   which is regular.

Hence D) should be the correct answer.

answered ago by Veteran (88.2k points) 15 58 293
selected ago by