The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.2k 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$.

asked in Theory of Computation by Veteran (59.6k points)
edited by | 2.2k views

6 Answers

+31 votes
Best answer
  1. Begin either with $0$ or $1$ 
    Regular expression $(0+1)(0+1)^*$               [ begin with $0$ or $1$ Anything ]
  2. End with $0$   
    regular expression $= (0+1)^*0$            [ Anything end with $0$ ]
        NFA                                                                          Equivalent DFA 
  3. End with $00$
    Regular expression $(0+1)^*00$        [Anything end with $00$ ]
    NFA                                                                               Equivalent DFA 
  4. Containing the substring
    Regular expression $= (0+1)^*00(0+1)^*$           [ Anything substring $00$ Anything ]
    NFA                                                                Equivalent DFA 

So, C is the correct answer.

answered by Veteran (55k points)
edited by
0
such a detailed explanation i think for this only GO is popular
+8 votes


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

so c is answer

answered by Veteran (61k points)
+7 votes
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
answered by Active (5k points)
0

10 also end with '0'

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

+6 votes
I go with C.

It contains all the strings which end up with 00.
answered by Boss (19.7k points)
edited by
+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
answered by Boss (14.3k points)
+5
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
c) ending with 00
answered by (249 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,903 questions
47,556 answers
146,275 comments
62,304 users