Finite automata

A machine that answers yes or no

From language to program

A regular expression describes a language. But the practical question is often: is this particular word in the language? We need an acceptor: a program that reads a word and answers yes or no.

We could write a program by hand for each expression. Instead, we shall mechanically produce the blueprints of a very simple machine, able to answer for any expression:

This machine reads the letters of the word one by one, from left to right, never going back. At every moment, it is in one situation among a finite number of possible situations, called states. Each letter read makes it change state. When the word is over, the state it is in gives the answer.

A first example

Over $\Sigma = \{a, b\}$, let us recognise the language $\{a\}$, which contains a single word: $a$. There are three situations:

• 0: nothing has been read yet. If the word stops here, the answer is no ($\varepsilon$ is not $a$).
• 1: exactly $a$ has been read. If the word stops here, the answer is yes.
• 2: something else has been read. Whatever happens next, the answer will be no.

Each state is drawn as a circle and each change of state as an arrow labelled with the letter read. The incoming arrow marks the starting state, called initial. The double circle marks the states where the answer is yes, called final (in French, the plural finals rather than finaux is the usage in language theory).

For the word $ab$: we start from 0, read $a$ and go to 1, read $b$ and go to 2. The word is over, 2 is not final: $ab$ is rejected.

Keeping only what is useful

Of the six transitions of this automaton, only one leads to a yes. State 2 is only there to say “it's lost”. If we agree that a blocked machine, which finds no arrow for the letter read, rejects the word, we can remove it:

This automaton recognises the same language, and it is easier to read. Each drawing has its own interest, and we shall learn to go from one to the other.

Definitions

Finite automaton

We give a single definition, the most general one, and we shall restrict it afterwards.

The size of the automaton, written $|A|$, is its number of states.

Nothing forbids several initial states, several transitions with the same origin and the same letter, or spontaneous transitions. This is the freest form, and we name the forms after what they allow:

Paths and recognised language

The path of length zero, which stays in state $q_0$, has label $\varepsilon$. So $\varepsilon \in L(A)$ as soon as some state is both initial and final.

Two automata that recognise the same language are called equivalent.

Three examples

A DFA. The words that have an even number of $a$. Two situations are enough: “even so far” (P, pair) and “odd so far” (I, impair). Reading $a$ changes the parity, reading $b$ does not.

An NFA. The words whose second-to-last letter is an $a$, that is, $(a + b)^* a (a + b)$.

From state 0, reading $a$, we can stay in 0 or go to 1: there is a choice. The automaton “guesses” that this $a$ is the second-to-last letter. The word is accepted if there is one way of guessing right. For $aab$, the path $0 \xrightarrow{a} 0 \xrightarrow{a} 1 \xrightarrow{b} 2$ is successful: the word is accepted. Other paths with the same label fail ($0 \xrightarrow{a} 1 \xrightarrow{a} 2$, then stuck on $b$), but that does not matter: one is enough.

An $\varepsilon$-NFA. The language $a^*b^*c^*$: some $a$, then some $b$, then some $c$, each any number of times.

We loop on the $a$ in 0, then move without reading anything to 1 to loop on the $b$, then to 2 for the $c$. The word $ac$ is accepted by the path $0 \xrightarrow{a} 0 \xrightarrow{\varepsilon} 1 \xrightarrow{\varepsilon} 2 \xrightarrow{c} 2$.

Nondeterministic does not mean “not deterministic”

A DFA is a special case of NFA, which is a special case of $\varepsilon$-NFA:

The second-to-last letter automaton, on the other hand, is an NFA that is not deterministic. In chapter 4 we shall learn how to turn it into an equivalent DFA.

Running an automaton

A DFA: a single run

In a DFA, there is never a choice: for each state and each letter, at most one transition. We then write $\delta(p, a) = q$ for the transition $p \xrightarrow{a} q$, and $\delta$ is a partial function from $Q \times \Sigma$ to $Q$. The run can be programmed in a few lines:

def accepte_dfa(automate, mot):
    etat = automate.initial
    for lettre in mot:
        if (etat, lettre) not in automate.delta:
            return False              # stuck: rejected
        etat = automate.delta[(etat, lettre)]
    return etat in automate.finals

The running time is proportional to the length of the word, and the memory used is one variable: the current state. This is why we want DFAs.

An NFA: all runs at once

In an NFA, there can be several paths for the same word. Trying all paths one by one costs, in the worst case, exponential time. It is better to follow the set of states we may be in:

def accepte_nfa(automate, mot):
    courants = set(automate.initiaux)
    for lettre in mot:
        courants = {q for p in courants
                      for q in automate.successeurs(p, lettre)}
    return any(q in automate.finals for q in courants)

For the second-to-last letter automaton and the word $aab$: $\{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{a} \{0, 1, 2\} \xrightarrow{b} \{0, 2\}$. The final set contains 2: the word is accepted.

Each step costs at most $|Q|^2$ operations: it is polynomial, but the “memory” is no longer a state, it is a set of states. Remember this idea: it is exactly the idea behind determinisation, in the next chapter.

The vocabulary of states

Accessible, co-accessible, useful

Here, state 3 is not accessible: no path leads to it from 0. State 4 is not co-accessible: we can enter it, but we never get out of it towards 2. States 0, 1 and 2 are useful.

Trimming an automaton means removing its useless states and the transitions that touch them. This does not change the recognised language, since these states are on no successful path. The algorithm is a graph traversal: we mark the accessible states by a traversal from $I$, the co-accessible states by a traversal from $F$ following the arrows backwards, and we keep the intersection.

Complete

A complete DFA has exactly one transition per state and per letter; its function $\delta$ is then total. To complete an automaton, we add a sink state, not final, which loops on all letters, and we send all the missing transitions to it.

Both automata recognise $ab^*$. Completing does not change the language: the sink is not co-accessible, so no successful path goes through it. Trimming and completing are two inverse operations: trimming the complete automaton removes the sink.

What next?

We have two ways of describing languages: regular expressions, which define $\mathrm{Rat}$, and finite automata, which define $\mathrm{Rec}$. The goal of the next two chapters is to show that these are the same languages, and to know how to go from one to the other:

• chapter 4: from an expression to an automaton, then to a DFA. Hence $\mathrm{Rat} \subseteq \mathrm{Rec}$;
• chapter 5: from an automaton to an expression. Hence $\mathrm{Rec} \subseteq \mathrm{Rat}$.