The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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 ?

asked in Theory of Computation by Veteran (12.6k points)
edited by | 104 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.

1 Answer

+2 votes
Best answer

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 by Veteran (100k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,210 questions
40,894 answers
39,793 users