Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 61 ยท Lexical Analysis

Finite Automata: DFA and NFA

Understand DFAs and NFAs, transition tables and dead states, and simulate both in Python to recognize identifiers, numbers and patterns like (a|b)*abb.

A regular expression says what a token looks like. A finite automaton says how to check it, one character at a time, using nothing but a small fixed amount of memory. It is a machine with a handful of states, a pointer to the current state, and rules that say which state to move to when the next character arrives. When the input ends, the machine either accepts the text or rejects it.

This is the engine under every lexer. Lex, Flex and the regular expression libraries of many languages turn patterns into automata, and a scanner is just an automaton in a loop. In this lesson you meet the two kinds, the deterministic (DFA) and the nondeterministic (NFA), and simulate both in Python. In the next lesson you will build them automatically from regular expressions. Pattern syntax is covered in Regular Expressions for Lexers.

DFA: the deterministic machine

A deterministic finite automaton has five parts:

  1. a finite set of states,
  2. an alphabet of input symbols,
  3. a transition function: for a state and a symbol, exactly one next state (or none),
  4. one start state,
  5. a set of accepting states.

To run it, put a marker on the start state and read the input left to right, moving the marker along the transition for each character. If the input ends while the marker is on an accepting state, the text is accepted. If there is no transition for a character, the machine is stuck in an implicit dead state and the text is rejected, whatever follows.

Here is the DFA for Tiny identifiers: a letter or underscore, then any letters, digits or underscores.

flowchart LR
    S0(("S0")) -->|"letter"| S1((("S1")))
    S1 -->|"letter, digit"| S1

Start in S0. The double circle S1 accepts. Any other character has no arrow, which means "dead".

Two features make this a DFA. There is only one start state, and from every state each input has at most one arrow. A machine like this is deterministic: at any moment you know exactly what it will do, so simulating it costs one table lookup per character, and that is why scanners built from DFAs are so fast.

The transition table

Diagrams are for people. Programs store the same thing as a transition table, where a row is a state and a column is an input class:

State letter digit other
S0 (start) S1 dead dead
S1 (accepting) S1 S1 dead

Notice that we group characters into classes (letter, digit, other) rather than listing every character. A real lexer does this too, otherwise a 256-column table would be mostly repetition.

Simulating a DFA in Python

The simulator is almost embarrassingly short: keep the current state, look up the next one, stop if there is none. The class below also prints the path of states, so you can watch the machine think. It includes a second automaton for numbers (an integer, optionally followed by a dot and more digits), and a method that finds the longest accepted prefix of a text, which is how a lexer uses a DFA in practice: run until the machine dies, then remember the last time it was in an accepting state.

Python DFAs for identifiers and numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the traces. For 9lives, the machine dies on the very first character, because S0 has no arrow for a digit. For a-b it reaches S1, then dies at -. The empty string stays in S0, which is not accepting, so it is rejected: a token needs at least one character.

The number automaton rejects 3. because the path ends in the dot state, which is not accepting. A number needs digits after the dot. Yet look at the last line of output. In the text 7. x1, the scanner does not give up on 7.: it reports NUMBER '7', and the leftover . becomes an error. The DFA ran past the 7, entered the non-accepting dot state, and died at the space, so the scanner backs up to the last accepting position (right after the 7). That backing up is the whole trick of longest-match lexing with DFAs. Compare it with the .5 case, where the leading dot makes the number machine die immediately.

NFA: the machine that can guess

Sometimes a rule is easier to say if the machine may have several choices. A nondeterministic finite automaton relaxes the DFA in two ways:

  • from a state, one input symbol may lead to several states, or to none;
  • it may have epsilon (ฮต) transitions, moves that consume no input at all.

How can a machine "choose"? The definition is that an NFA accepts a text if there exists some sequence of choices that ends in an accepting state. You can think of it as a machine that magically guesses right, or as one that explores every possibility at once.

Example: the language of strings over a and b that end in abb, written (a|b)*abb. The NFA loops in state 0 reading anything. Whenever it sees an a, it also bets that this is the start of the final abb and moves to state 1:

flowchart LR
    q0(("0")) -->|"a, b"| q0
    q0 -->|"a"| q1(("1"))
    q1 -->|"b"| q2(("2"))
    q2 -->|"b"| q3((("3")))

State 0 has two arrows for a: one that stays and one that bets the ending has begun.

A DFA for the same language needs more states, because it has to remember how much of abb it has seen so far. The NFA is much easier to write down, which is exactly why compilers like to build NFAs first.

Simulating an NFA

Nobody has a computer that guesses, so we simulate all the possibilities at once: keep a set of current states. For each input character, replace the set with every state reachable from any member by that character. Before and after each step, add everything reachable by ฮต-moves, which is called the epsilon closure. The text is accepted if the final set contains an accepting state.

Python Simulating NFAs with sets of states

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trace for aabb is worth reading line by line. After the first a, the set is [0, 1]: the machine is both still looping and betting on the ending. The next a gives the same set. When b arrives, state 1 moves to 2 while state 0 stays: [0, 2]. A second b brings state 2 to 3, the accepting state, and the text is accepted. For abba the bet fails: after the final a the set no longer contains 3.

The second automaton, for a*b*, uses an ฮต-move: from state 0 you can jump to state 1 without reading anything, which is how "zero a's" turns into "straight to the b's". This is why the closure is applied at the start. The empty string is accepted, because the closure of state 0 includes state 1.

DFA versus NFA

DFA NFA
Choices per input exactly one (or dead) any number
ฮต-moves no yes
Easy to build from a regex harder easy
Running time per character one lookup work proportional to the number of active states
Number of states possibly large usually small

The surprising fact is that they have the same power: every NFA can be converted to a DFA that accepts the same language (the DFA may have exponentially more states in the worst case, but in practice it is usually modest). So NFAs add convenience, not capability. The conversion is called the subset construction, and you will implement it in the next lesson.

The pipeline used by real scanner generators is therefore:

  1. write token patterns as regular expressions,
  2. convert each regex to an NFA (Thompson's construction),
  3. combine them and convert the result to a DFA (subset construction),
  4. minimize the DFA, and
  5. run the DFA as a table-driven loop with the longest-match rule above.

Limits of finite automata

A finite automaton has no memory except its current state, so it cannot count without bound. The language of balanced parentheses (((...))) needs a counter that grows with the input, which a machine with a fixed number of states cannot do. That is precisely why lexers handle words and numbers, while nested structure is the job of the parser and of context-free grammars.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What makes a finite automaton deterministic?

    In a DFA the next state is completely determined by the current state and the input symbol. NFAs allow several choices and ฮต-moves.
  2. 2. In the identifier DFA, what happens with the input 9lives?

    From the start state S0 only a letter leads anywhere. A digit leads to the dead state, so the text is rejected immediately.
  3. 3. How does a lexer use a DFA to find the longest token?

    Remembering the last accepting position, then backing up to it, implements maximal munch in a single left-to-right pass.
  4. 4. How do you simulate an NFA on a normal computer?

    Tracking the set of possible states (with epsilon closure) explores every choice at once, so no guessing is needed.
  5. 5. Which language is beyond the power of any finite automaton?

    Matching arbitrary nesting needs unbounded counting, but an automaton has only a fixed number of states. That is the job of a parser.

Summary

  • A finite automaton reads text one character at a time, moving between a fixed set of states; it accepts if it ends in an accepting state.
  • A DFA has exactly one move per state and symbol, so it is fast: one table lookup per character; missing transitions mean the dead state.
  • Transition tables group characters into classes such as letter, digit and other.
  • Lexers run a DFA until it dies and back up to the last accepting position to get the longest match.
  • An NFA may have several moves for one symbol and ฮต-moves; it is simulated with a set of states and ฮต-closure.
  • NFAs and DFAs recognize the same languages, and NFAs are much easier to build from regular expressions.
  • Finite automata cannot count without bound, so nested structure needs a parser.

Next: From Regex to NFA to DFA