edited by
24,889 views
117 votes
117 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?

  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
edited by

6 Answers

Best answer
162 votes
162 votes

Correct Option: A

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:

edited by
23 votes
23 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.

5 votes
5 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
5 votes
5 votes

In L1 any string “w” must satisfy the condition:
{Number of occurrences of (110)} ≥ {Number of occurrences of (011)}
Lets analyse the language, consider a string in which occurrence of (110) is more than one.
The following possibilities are: {1100110, 1101110, 110110, ….}
Please observe whenever strings start with “11” then in every situation whatever comes after “11” the string will never violate the condition. So strings of the form 11(0+1)* will always satisfy the condition.
Consider a string in which occurrence of (011) is more than one.
The following possibilities are: {011011, 0111011, 0110011, ….}
In the following possibilities please observe that number of occurrence “011” is two but number of occurrence of (110) is one, which violate the conditions.
If we add “0” in every string mentioned above, i.e. {0110110, 01110110, 01100110, ….} Now, observe that number of occurrence “011” and the number of occurrence of (110) both are equal, which satisfies the conditions.
With these analysis, we can make the DFA , which is mentioned below.

But language L2 requires infinite comparison to count the occurrences of (000’s) and (111’s), hence it is not regular.

Answer:

Related questions

43 votes
43 votes
3 answers
1
91 votes
91 votes
5 answers
2