How to use the finite automaton string tester
- Write the automaton in the box: a start: line, an accept: line and one line for each move, such as q0, a -> q0, q1.
- Use eps (or ε) for a move that reads no symbol. A move with several targets lists them after the arrow.
- List the strings to test, one per line, and write ε for the empty string. Add a string to trace if you want to see each step.
- Read which strings are accepted, the trace of states after every symbol, and the equivalent DFA table if you kept that box ticked.
Formula
state set after a symbol = all states reachable from the current set by that symbol, plus empty moves
accepted if the final set contains an accepting state
subset construction: each DFA state is a set of automaton states; its move on a symbol is the set reached
A DFA has exactly one move for each state and symbol and no empty moves; anything else is an NFA. A missing move simply leads nowhere, so the set of states can become empty, which rejects.
Strings that end in abb
The example machine has states q0 to q3 and accepts strings over a and b that end in abb. Of the six test strings abb, aabb, babb, ab, abba and the empty string, the first three are accepted and the last three rejected, so the headline reads 3 of 6.
Tracing aabb gives the state sets {q0}, {q0,q1}, {q0,q1}, {q0,q2} and {q0,q3}, and the last set contains the accepting state q3. The equivalent DFA has 4 states: {q0}, {q0,q1}, {q0,q2} and {q0,q3}, the last one accepting.
Why NFAs and DFAs describe the same languages
An NFA may guess among several moves and accepts if any guess works, which makes some machines much shorter to write. A DFA has no guessing, so it is simple to run. Subset construction shows that every NFA can be turned into a DFA, though the DFA may need exponentially many states in the worst case; the page lists the table when it has no more than 128 states.
The sets of strings these machines accept are exactly the regular languages, the ones a regular expression can describe. You can check a pattern against the same strings in the Regex Tester, and explore logic with the Truth Table Generator.
Input format
State names are words without spaces or commas. A symbol is a single character, and any character except space and comma can be used, so the alphabet is read from the moves. Lines starting with # are notes. Up to 40 states and 100 test strings are accepted.
Assumptions and limits
- Symbols are single characters; longer tokens are not supported, apart from the words eps and ε.
- A test string containing a character that is not a symbol of the machine is rejected and the character is named.
- The DFA is built from the start state and includes only states that can be reached, plus the dead state {} when needed.
- The DFA is not minimized, so it may have more states than the smallest possible one.
- The tests compare every string up to length 7 with Python's regular expression engine and a separate simulation.
Frequently asked questions
What does the empty set in a trace mean?
No state can be reached, so the string is rejected whatever follows. The DFA calls this the dead state.
How do I write the empty string as a test?
Type ε alone on a line.
Why does my DFA have more states than I expected?
Subset construction can create many sets, and the page does not merge equivalent states. Minimizing is a separate step.
Can a state be both the start and an accepting state?
Yes. Then the empty string is accepted, as in the even number of a example.