NFA Simulator

A nondeterministic finite automaton or NFA is a finite-state machine that may nondeterministically move to any of a set of states as it reads characters from a string.

Each input consists of a table describing the NFA, and a quoted input string, like so:

    | a | b | c |
→ 0 |{0}|{0}|{0,1}|
  1 |{2}| ∅ |  ∅ |
  2 | ∅ |{3}|  ∅ |
 F3 | ∅ | ∅ | ∅ |
acbcab

In this table, we can find the following information:

• There are four states, called 0, 1, 2, and 3.
  • States are always digits 0-9. There may be up to 10 states.
• There are three characters in the input alphabet: a, b, and c.
  • Input characters may be lowercase letters a-z or digits 0-9.
• The table entries describe the set of states the NFA may transition to for each (current state, character) pair.
  • For example, if the current state is 0, and a c is read, the set of possible next states is {0,1}.
• The row describing state 0 is marked with → so it is the initial state. There is exactly one initial state.
• The row describing state 3 is marked with F so it is an accept state. There may be multiple accept states, or none at all.

Use the table to move the NFA between sets of valid states by feeding it characters from the input string. Once the set of possible states is the empty set, it remains so.

In our example:

• The initial state is 0. The first character is a. Looking at the table, we see the new set of possible states is {0}, so the NFA must be in state 0.
• The current state is 0. The next character is c. Looking at the table, we see that the set of possible next states is {0,1}. Thus, the NFA may nondeterministically move to either 0 or 1. or, alternatively, its set of possible locations is {0,1}.
• The current state is either 0 or 1. The next character is b. Looking at the table, we see that if the state had been 0, it can be 0 next, while if it had been 1, it has no next state -- and that computation path dies. Thus, the set of reachable states after seeing substring acb is {0,1}.

Finally, print on separate lines the set of reachable states after processing the entirety of each input string, followed by a space, followed by either Accept (if the NFA can reach any accept state by processing the string, or, in other words, if the final set of valid states contains an accept state) or Accept (otherwise). In this case, we may end at either 0 or 3 and one of them is an accept state (3), so we print {0,3} Accept.

There may be multiple input strings presented on separate lines; print their respective outputs on separate lines. When printing a set, sort its elements numerically and use ∅ to denote the empty set. The empty string in the input is denoted by ε.

External links: Wikipedia