I think L1 reduces to {0^{n}0^{m}1^{m}1^{k}}, 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 {0^{n}1^{k}}, which is regular.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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?**

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

**Is L1 regular ?**

+2 votes

Best answer

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

Given L1 : 0^{n+m} 1^{k+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 : 0^{x }1^{y} | x,y >= 2 which is regular.

**Hence D) should be the correct answer.**

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.3k
- Digital Logic 2k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 494
- Exam Queries 442
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,019 questions

44,592 answers

126,850 comments

43,663 users