GATE CSE 2014 Set 2 | Question: 36

Question

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?

• A. $L_1$ is regular but not $L_2$
• B. $L_2$ is regular but not $L_1$
• C. Both $L_1$ and $L_2$ are regular
• D. Neither $L_1$ nor $L_2$ are regular

Comments

https://cs.stackexchange.com/questions/12139/is-the-language-of-words-containing-equal-number-of-001-and-100-regular

---

#110 ≥ #011 is the acceptance condition for L1.

---

I think best question on regular language because of L1.

Answer 1

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

Comments

Yes due to relationship between 011 and 110  that occurrence of 011 and 110 would be equal

Answer 2

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*].                                                                                                                                

 

 

 

 

 

 

 

 

 

 

 

 

 

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.