The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+59 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

+89 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:

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)

+13 votes

+4 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

+3 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.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.1k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

49,845 questions

54,783 answers

189,424 comments

80,432 users