Notebook 2: NFA Reachable States

Step-by-step interactive visualization of NFA reachable state computation. Trace the active set of states for each input prefix using the blackboard example from the VVT course at UniUD.

NFA Reachable States

This notebook focuses on the set-valued transition function of an NFA. The automaton is the blackboard example from the finite-automata lecture: for each input prefix, the active set is the set of all states reachable by at least one run.

b b b a b b a a a q q2 q1 q4 q5 q3
Active states
Prefix Reachable states

What To Notice

For the default word bba, the reachable sets are: [ {q}, {q_2,q_4}, {q,q_1,q_5}, {q_1,q_3,q_4}. ]

The important point is the third step. When the final a is read, the branch currently in q disappears because there is no outgoing a-transition from q; the other branches continue and their successors are unioned together.