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.

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.