1.9k 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\}$

edited | 1.9k views
0
What is meant by "reachable" over here? Set of terminating states for the string 0011 or set of all the states that can be visited by 0011?

For eg, if q2 was the only state where 0011 could terminate, then the answer will be {q2} or {q0,q1,q2}? $q_0, q_1$ and $q_2$ are reachable from $q_0$ on input $0011$

Correct Answer: $A$

by Veteran (57k points)
edited
0
@Praveen Saini

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

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.

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...
0
$\delta^*(q,w)=$contains only those states which have a walk from state q labelled w.
0
how to solve it fastly

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

by Boss (14.4k points)
edited q0,q1 and q2 are reachable from q0 on input 0011.

hence, reachable states={q0,q1,q2}. Option A is correct.

by (471 points)