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

- $L_1$ is regular but not $L_2$
- $L_2$ is regular but not $L_1$
- Both $L_1$ and $L_2$ are regular
- Neither $L_1$ nor $L_2$ are regular

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

if only 110 is the string then number of oo1 is zero and number of 110 i 1

therefore 1>= 0 ,hence satisfied

117 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:

9

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.

0

@arjun sir thanks.

@akriti Moreover I would like to add point here

{ a^{n}b^{n} | 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^{n} y^{n} | 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^{n}b^{n} |^{ }n>0 } then only it is cfl Here actually u are comparing #a = #b

@Arjun sir plz kindly verify.

0

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?

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?

0

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

for aabba

Two way are there

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

x^{1}y^{1} = (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??

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 { x^{n} y^{n} | x,y belongs to (a+b)^{*, }n>0} means

{ x^{n} y^{n} | 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

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

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?

For L1 it would be 110011110011 or 11011011011 ?

For L2 it would be 000111000111 or 000000111111?

17 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

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

4 votes

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

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

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

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.