edited by
351 views
3 votes
3 votes

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 by

1 Answer

Best answer
2 votes
2 votes

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.

selected by

Related questions

0 votes
0 votes
1 answer
1
Deepak9000 asked Nov 27, 2023
201 views
Why is C is regular as it non regular as?Please help me with this confusion
0 votes
0 votes
1 answer
2
M_Umair_Khan42900 asked Dec 29, 2022
747 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)...
0 votes
0 votes
2 answers
4