Details
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
, and3
.-
States are always digits
0-9
. There may be up to 10 states.
-
States are always digits
-
There are three characters in the input alphabet:
a
,b
, andc
.-
Input characters may be lowercase letters
a-z
or digits0-9
.
-
Input characters may be lowercase letters
-
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}.
-
For example, if the current state is
-
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 withF
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 isa
. Looking at the table, we see the new set of possible states is{0}
, so the NFA must be in state0
. -
The current state is
0
. The next character isc
. Looking at the table, we see that the set of possible next states is{0,1}
. Thus, the NFA may nondeterministically move to either0
or1
. Or, alternatively, its set of possible locations is{0,1}
. -
The current state is either
0
or1
. The next character isb
. Looking at the table, we see that if the state had been0
, it can be0
next, while if it had been1
, it has no next state -- and that computation path dies. Thus, the set of reachable states after seeing substringacb
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