The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes

asked in Theory of Computation by Boss (8.4k points) | 103 views
both is regular
how $L_{1}$ is regular?
what is the answer given ?

 as u r saying l, m does not depend upon n and k but in the given condition it is mentioned dat..  m=l, m, n, k so all of them should accept equal no.  of l,m, n and k..!!

Praveen Saini can you explain L1 once

@ krati litoriya    m=l, m,n,k,l  >=1, it means m equals to l and value of m, n, k, l is greater than or equal to 1. Nowhere its written all m,l,n,k should be equal.

2 Answers

+4 votes
Best answer

L1 = {0n+m1k+l | m = l, m, n, k, l >=1}
We can write it as
L1 = {0n0m1k1l | m = l, m, n, k, l >=1},Since m and l does not depend upon n and k, we can fix its value as 1, and use n and k to take remaining 0's and 1's, so our language become..
L1 = {0n01k1 |  n, k >=1}Now we just need to check for any number of 0 followed by a 0, then any number of 1 followed by a 1, which is regular.

L2 = {0n(11)m | m,n >=0}
Any number of zeros followed by even number of 1's, its regular.

According to me option D is correct, both L1 and L2 are regular.

answered by Boss (7.5k points)
selected by
i write the ans as B bcoz i m not able to decide how L1 is regular in test but ans is given as D.
+2 votes



Please correct me if I am wrong 

answered by Junior (535 points)

Related questions

+2 votes
2 answers
0 votes
1 answer
0 votes
1 answer

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

33,712 questions
40,255 answers
38,881 users