GATE IT 2008 | Question: 5

Question

Which of the following regular expressions describes the language over$\{0, 1\}$ consisting of strings that contain exactly two $1$'s?

• A. $(0 + 1)^ * \ 11(0 + 1) ^*$
• B. $0 ^* \ 110 ^*$
• C. $0 ^* 10 ^* 10 ^*$
• D. $(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*$

Comments

"contain exactly two 1's"

So we need to restrict more generation of 1's.

A,D. (0+1)* present so no such restriction.

---

Options A and D are incorrect because they allow more than two 1's. Option B is also incorrect because it cannot generate strings like "1001". Option C, 0*10*10* correctly matches strings containing exactly two 1's, with any number of 0's before, between, or after them. Therefore, Option C is correct.

---

in hurry, someone can tick optoin D but can pump any number of 1's in starting itself.

Answer 1

• A. with at least $2$ consecutive $1$'s, any no of $0$'s and any no of $1$'s
• B. exactly two consecutive $1$'s
• C. exactly two $1$'s but need not be consecutive
• D. any no of $1$'s and $0$'s with at least two $1$'s

Hence, (C) is the correct option.

Comments

Manu Thakur sir, If this question will be asked in MSQ then B and C can be the answer?

---

No. Option B cannot generate 101

Answer 2

A. We can get any number of 1.

B.More strict .. means it is covering only one possibility of containing exactly two ones.eg. 0110 ,11  . But 0101 is also satisfying the condition which is not covered by option B.

C. It is covering all d possibility of containing exactly two one's . 101,11,0011,01010........

D. Any no. Of one we can take from here

 

So, answer is option C.

Comments

Thanks for the example

---

in question this is not mentioned that all string having two 1's so why both options B and C are not true ? because in B also only two 1's.

Answer 3

Draw the Deterministic finite automata with all the transitions for ∑ = {0,1} for no. of 1’s equal to two and get it’s corresponding Regular expression.

Answer 4

SINCE THE QUESTION ASKS FOR "STRINGS WITH EXACTLY TWO 1S" :

We solve as follows:

(A) and (D) options we see that it has (0+1)* which means that it can generate any no of 1s and 0s combination which completely violates our condition so both are wrong

Now coming to (B) and (C), IN (B) the 1s are forced nex to each other which means it misses on strings which has two 1s but both 1s are not together hence (C) is correct 

The language is defined as: "All strings over {0,1} that contain exactly two 1's."

Let's look at some valid strings that perfectly satisfy this definition:

• String 1: 101 (It has exactly two 1's)

• String 2: 01010 (It has exactly two 1's)

• String 3: 10001 (It has exactly two 1's)

Now, try to generate any of these three strings using Trap B (0*110*):

• You cannot. Because the two 1's in the expression are written directly next to each other (11), Trap B strictly forces the two 1's to be physically adjacent in every single string it creates.

By forcing the 1's to stick together, Trap B completely leaves out an infinite number of valid strings where the two 1's are separated by zeroes.

 

SUMMARY:

• What 0*110* describes: The language of strings containing exactly two 1's that must appear consecutively (right next to each other).

• What 0*10*10* describes: The true language of strings containing exactly two 1's anywhere in the string, separated by any number of zeroes.

When a regular expression leaves out valid strings that belong to the definition, it is incorrect, even if every string it does manage to generate happens to be legal!