edited by
24,921 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

1 votes
1 votes
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
0 votes
0 votes

yes the answer is A here you can take a look at my answer 

what we sholud notice is that question asks for as any sequences of 110 as 011

in other words

so we need not care and accept anything until the string we are passing through our dfa has an occurrence of 

011

one key property to notice is that adding a 0 to the end of 011 makes it 0110 and acceptable for us.

so we have to ensure that the string we are passing through our dfa is accepting as long as [(011).1*] is not encountered 

when that is encountered we move to the dead state IN DEAD STATE if the string still has characters and it implies to our terms we send it to one of our accepting states. 

it is essentially a complement of [(011).1*].                                                                                                                           l1 dfa     

 

 

 

 

 

 

 

 

 

 

 

 

 

no for l2 :

we have a similar condition

but here one thing to observe is that both the substrings are not related to each other hence we can say that  we need to implement a counting logic for 111 and 000 and go to a accepting state whenever the condition described above is met.

it is same as 

dpda where there are same no. of a’s and same no. of b’s.

 

Answer:

Related questions

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