The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+50 votes
4.8k views

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?

  1. $L_1$ is regular but not $L_2$
  2. $L_2$ is regular but not $L_1$
  3. Both $L_1$ and $L_2$ are regular
  4. Neither $L_1$ nor $L_2$ are regular
asked in Theory of Computation by Veteran (101k points)
edited by | 4.8k views
0
if we take only 110 now how L1 is regualar?
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
0
w has at least as many occurrences of (110)′s as (011)′s

can anyone explain what this statement mean i am little bit confused .
0
Very good question.
0
Occurrence of (110)'s >= occurrence of (011)'s

This is what it means?

4 Answers

+75 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:



 

answered by Boss (18.1k points)
edited by
0
yess..wrt to that only
0

wrt to { xn yn | x,y belongs to (a+b)*, n>0}

for aabba

Two way are there

x1y1 = (eps)1(aabba)1 =aabba    //set constraint x,y belongs to (a+b)*

x1y1 = (aabba)1(eps)1 =aabba

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??
0

Yes U r right.

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

 { xn yn | 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
What about L2... Why is ut not regular
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)
0
0
sir, i am not stilll able to understand why division is not possible,can you explain again?
0
But in L1 if we remove atleast than it will not be regular
Am i right
+10 votes

L1 is regular let us consider the string 011011011011 In this string, number of occurrences of 011 are 4 but when we see here 110 is also occurred and the number of occurrence of 110 is 3. Note that if i add a 0 at the last of string we can have same number of occurrences of 011 and 110 so this string is accepted. We can say if the string is ending with 011 so by appending a 0 we can make 110 also. Now string2: 110110110110 in this number of occurrences of 110 is 4 and 011 is 3 which already satisfy the condition So we can observe here that whenever 110 will be there string will be accepted So with this idea we can build an automata for this. Therefore, it is regular.

answered by Loyal (8.4k points)
+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
answered by Boss (10.3k points)
0
What in case string is 11000110.

Here no of 110's is 2 and no of 011's is 1.How its going to accept the string and on what bsis it will count to accept the string.
Please explain.
+1 vote
Option A is correct

As the relationship between 011 and 110

U cannot have 2 instances of any 1 without the other

Thus making it regular

 

Where as in case of l2 language the same is not true
answered by Junior (535 points)
0
Yes due to relationship between 011 and 110  that occurrence of 011 and 110 would be equal
Answer:

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

39,848 questions
46,815 answers
141,152 comments
59,065 users