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

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:

Comments

But from the given DFA 11 is accepted only at q5.
So how is 11 011 011 accepted.
Is there any mistake in the DFA? Sorry but i dont understand how after 11 011 and 011 is read.

---

Once it reads 11 as the first two letters of a string, state reached is q5. Now whatever is in the input string is just read without a state change. This is represented by the self loop for 0,1 in q5.

---

K got it.

---

I understand the concept. and you explained it beautifully.

but in DFA something wrong is at state q5.

that accept the string "110"  [ one occurence of 110 and no occurence of 011] .

some correction is required at state q5 for the transition on symbol 0

---

110 is to be accepted. #110 ≥ #011 is the acceptance condition for L1.

---

got it . i missed the word atleast.

---

What will be its correct answer? I have doubt between (b) & (c). please explain.

---

Answer is C. Any string over a and b can be split in to two parts such that number of a's on left part is equal to number of b's on right part.

a - x = ⋴, y = a

b - x = b, y = ⋴

aa - x = ⋴, y = aa

ab - x = a, y = b

ba - x = b, y = a

bb - x = bb, y = ⋴

.....

ababbba - x = abab, y = bba

,,,

---

can we say regular expression for L1 is (110)(0+1)*(011) + (011)(0+1)*(110) + Epsilon. Is it correct ?

---

Why it is sigma kleen star when we have to make comparison between no of a and no of b it should be done by pda na and it should be cfl bt nt regular

---

@arjun sir,how is the correct option C?can you explain??i did nt get it from the figure

---

and moreover,i dun fing C option even logical,

lets take aab ,this word is part of sigma kleen but here no. of a != no. of b,so how can you say that correct option is C

answr should be B because this language is CFL but not regular

---

below ques ans should be op(b) i.e cfl but not regular  bez it is a problem of counting compairsion without order

---

Arjun sir is abs. correct here option C is only ans.

@dileswar @Akriti @Kaluti

Plz read it carefully

Any string over a and b can be split in to two parts such that number of a's on left part is equal to number of b's on right part. 

Example:-aab

Left Part x =a       //#a=1

Right Part y=ab    //#b=1

Note:- If u still not agree then comment ur strings from E* .i will divide them.

---

so,do you mean this language is regular??

---

100% Regular and it is E*.

---

@rajesh ,then the langauge { aⁿbⁿ | a,b belongs to (a+b)^*, n>0} should also be regular as here also,we can divide them into groups and say number of A = number of B.

can you tell the difference??

---

@Akriti A string is divided because $L$ is defined as $xy$ where $x$ and $y$ can by any possible string. For your language there is only one string and hence no division possible. To become an element of a set one needs to just satisfy the set definition - any how just satisfy it.

---

ok.i understood arjun sir.

so sir,if any other condition instead of equality of a and b would have been given,then also we can divide like this..??

---

For set definition there is no general rule- it depends on how a given set is defined. I have seen many people by-hearting many such rules- but GATE can make any number of questions where no such rule follows. Only way is to read and understand the given set definition and solve it. Of course having solved many problems will help - but never by heart any "conditions" as given by many in the above comments.

---

thankyou sir:-)

---

@arjun sir thanks.

@akriti Moreover I would like to add point here

{ aⁿbⁿ | a,b belongs to (a+b)^*, n>0}  we never write set condition like this here "a,b belongs to (a+b)^{* "}  does not make any meaningful sense bcz on left side of bar of set representation also u have used a,b.

anyhow it is trivial to say "a,b belongs to (a+b)^{* "} .

->>You may write like this { xⁿ yⁿ | x,y belongs to (a+b)^*, n>0}

Now for this also L=E* .

Note :-http://gatecse.in/category/theory-of-computation/page/2/  Link is best to Understand this kind of question.

if it is { aⁿbⁿ | n>0 } then only it is cfl Here actually u are comparing #a = #b 

@Arjun sir plz kindly verify.

---

yea..dts not correct.thanks

and i too had same question in mind that u asked.

what if the string is odd,how wil u divide it?as now one more constraint is there,that is both 'x' and 'y' should have same length.

for example-aabba

how will you divide?

---

r u talking wrt to { xⁿ yⁿ | x,y belongs to (a+b)^*, n>0} ??

---

yess..wrt to that only

---

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

for aabba

Two way are there

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

x¹y¹ = (aabba)¹(eps)¹ =aabba

---

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

---

Yes U r right.

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

 { xⁿ yⁿ | 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

---

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

---

What about L2... Why is ut not regular

---

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)

---

@arjun sir-:

https://gateoverflow.in/158766/modified-gate2014-2-36

---

sir, i am not stilll able to understand why division is not possible,can you explain again?

---

But in L1 if we remove atleast than it will not be regular
Am i right

---

How the concerned strings for L1 and L2 would be written.. Please correct me.

For L1 it would be 110011110011 or 11011011011 ?

For L2 it would be 000111000111 or 000000111111?

---

how can i say in general??i.e A,B binary string and we have to check equal no of A and B

then Can we conclude lang will be regular if and only if A,B related as AA it must contain one B and BB must contain one A?

---

can it be generalized that any overlapping pattern will be regular?

---

Can someone help me with DFA Constructed for L$_{1}$?

---

Is it possible to analyze this fact during GATE exam , or am I the one who is struggling to find it

---

Can someone pls explain how by identifying the relation between 011′ and 110′s we can conclude that we only need a finite number of states to check for acceptance of any word in this language ?

---

i am also thinking same

---

Nah Brother Many will not be able to think instantly during exam

Answer 2

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.

Comments

can this method work with say : 110110011011?

Answer 3

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

Comments

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.

---

what about 011110

Answer 4

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.