The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+54 votes

Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ $\text{s as} $ $(111)'$ $\text{s} \}$. Which one of the following is TRUE?

- $L_1$ is regular but not $L_2$
- $L_2$ is regular but not $L_1$
- Both $L_1$ and $L_2$ are regular
- Neither $L_1$ nor $L_2$ are regular

0

110 is accepted because the grammar is saying that number of 110 should be >= number of 001.

if only 110 is the string then number of oo1 is zero and number of 110 i 1

therefore 1>= 0 ,hence satisfied

if only 110 is the string then number of oo1 is zero and number of 110 i 1

therefore 1>= 0 ,hence satisfied

+83 votes

Best answer

(**A**) is True. Though at first look both $L_1$ and $L_2$ looks non-regular, $L_1$ is in fact regular. The reason is the relation between $110$ and $011$.

We cannot have two $110'$s in a string without a $011$ or vice verse. And this would mean that we only need a finite number of states to check for acceptance of any word in this language.

That was just an intuitive explanation. Now I say that L contains all binary strings starting with $11$. Yes, if a binary string starts with $11$, it can never have more no. of $011$ than $110$.

Lets take an example:

$11 \ 011 \ 011$ -There are two $011'$s. But there are also two $110$'s. Similarly for any binary string starting with $11$.

Using this property, DFA for $L_1$ can be constructed as follows:

0

yes..then it looks regular

and if in this language,#a in x=# b in y condition was there..then still would it have been regular.i dun think so..what do you say??

and if in this language,#a in x=# b in y condition was there..then still would it have been regular.i dun think so..what do you say??

0

Yes U r right.

If we add another constraint to { x^{n} y^{n} | x,y belongs to (a+b)^{*, }n>0} means

{ x^{n} y^{n} | x,y belongs to (a+b)^{*, }n>0 and (no of a in x= no. of b in y) }

then this is non regular as here we have to handle 2 conditions simultaneously

1) n>0 2)no of a in x= no. of b in y //which makes it non-regular

0

Yes in that case here two conditions have to be simultaneously handled here equality and no of a in x equals to no of b in y therefore non regular in that case

0

because to conclude equal number of 000 and 111 we will need a stack and so it is DCFL it will form a language of kind (000^n 111^n) or (111^n 000^n)

+12 votes

+4 votes

Option A )

it is clear that L2 is not a regular language .

Now L1 , this language can be rewrite like this way the number of 1`s can stay together atmost 11 (two 1`s) if more than 2 1`s occur then it have to be split with 0 and if before the sequence 11 if there is any 0 then it should ends with 0 .

eg : 0110110110110110 (have to end with 0)

110110110110110

it is clear that L2 is not a regular language .

Now L1 , this language can be rewrite like this way the number of 1`s can stay together atmost 11 (two 1`s) if more than 2 1`s occur then it have to be split with 0 and if before the sequence 11 if there is any 0 then it should ends with 0 .

eg : 0110110110110110 (have to end with 0)

110110110110110

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 5.9k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 588
- Exam Queries 568
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,071 questions

53,206 answers

184,561 comments

70,424 users