The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+13 votes
1.3k views

Consider the finite automaton in the following figure:

What is the set of reachable states for the input string $0011$?

  1. {$q_0,q_1,q_2$}
  2. {$q_0,q_1$}
  3. {$q_0,q_1,q_2,q_3$}
  4. {$q_3$}
asked in Theory of Computation by Veteran (112k points)
edited by | 1.3k views

2 Answers

+24 votes
Best answer

                                        

$q_0, q_1$ and $q_2$ are reachable from $q_0$ on input $0011$

answered by Veteran (55.4k points)
edited by
0
@Praveen Saini

Can't we move like this q0,q0,q0,q1 because q0 has both 0,1 inputs
+1

@ Divya Bharti

It is NFA. So, if we consider for all possibility then answer is q0,q1,q2

+1

@Praveen Saini Sir, can we also convert it to DFA and check, well, I did convert to DFA and found out that string 0011 end up in state {q0 q1 q2} I just want to confirm can we convert NFA to DFA and check it?

+1
yes it will work fine.
0
@praveen

1.How to tackle this type of problem.

2.why not Q3 is considered as it is the final state as any string accepted by automata must end up at final state.

 

Please suggest

Thanks
0
Question is not about accept and reject of input
0
@Mr. Praveen, Can you please justify why we should not reach the final state?

Isn't it mandatory to reach final state for a given input string? I'm in doubt...
+10 votes

qo,q1,q2 can be reached in this nfa by enumerating all the possibilities

answered by Boss (14.4k points)
edited by
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

44,491 questions
49,940 answers
165,706 comments
65,911 users