3k views

The above DFA accepts the set of all strings over $\{0,1\}$ that

1. begin either with $0$ or $1$.

2. end with $0$.

3. end with $00$.

4. contain the substring $00$.

edited | 3k views

1. Begin either with $0$ or $1$
Regular expression $:(0+1)(0+1)^*$
2. End with $0$
Regular expression $: (0+1)^*0$

3. End with $00$
Regular expression $:(0+1)^*00$

4. Containing the substring $00$
Regular expression $: (0+1)^*00(0+1)^*$

So, C is the correct answer.

by Veteran (57k points)
edited by
+4
such a detailed explanation i think for this only GO is popular
0

@Praveen Saini sir it contains 00 as a substring is okk , but cant't we say end with 0?

+1
Ankit , No as ended with 0, also accept, 0, 10,..

1. begin either with 0 or 1  contain '0' and '1' which is not accepted so false

2. end with 0 contain  '110' which  is not accepted.so false

3. end with 00 contain True here

4. contain the substring 00. contain 00101 which is not accepted i.e. take  any string conatin  the substring 00 and end with 1. so false

by Veteran (63k points)
I'll prove it by taking 'false string'

A: Begin with '0' or '1' False String: 11,111,etc.

B: End with '0'  False String: 10,110,etc.

D: Contain substring '00': 1001,10001,etc.

So remaining option is C
by Active (4.9k points)
0

10 also end with '0'

End with '0'  False String: 10,110,etc.

I go with C.

It contains all the strings which end up with 00.
by Boss (19.9k points)
edited
+1 vote
End with 00 and end with 0 both are correct but the most appropriate is ending with 00 More the information about language is given the more you will find easier to distinguish between them and after all it is not a minimal dfa for strings ending with 0..so the option ending with 0 is quite inappropriate
by Boss (14.4k points)
+6
No. Ending with 0 is wrong- because it is not accepting all strings ending with 0- 010 for example.
0
@Arjun Sir....though answer is C..in test it is showing A as right answer, kindly correct the key in GO test on previous gate questions.....it is the time when such things scares me the most...
+1 vote

Recognize the language accepted by the given DFA i.e. L={00,100,000,1100,0100,1000,0000.......}

Hence, DFA accepted all strings which is ends with 00. Option C is correct.

Now counter examples for other options:

1. Option A is false, as the DFA is not accepting the string “10”.

2. Option B is false as the DFA is not accepting the string “10” .

3. Option D is false as the DFA doesn’t accept the string “1001” which has “00” as substring.

by (471 points)
–1 vote
c) ending with 00
by (269 points)