Case Study: Finite Automata

Graphs are a foundational data structure in many areas of computer science. To close this portion of the course, we'll take a look at a particular application of graphs towards an older theme: program correctness. We'll use graphs to develop a simple model from the theory of computation, the finite automata. While simple, the model captures a wide variety of computations that we might consider in a computer program. This model will put together everything we have learned so far towards the task of using mathematics productively in programming and tease at what future courses in the foundations of computer science will cover!

Strings

A finite automata is an abstract machine that consumes strings of characters as input and produces a boolean, a yes or no answer, as output. Before we explore the finite automata itself, we must first formalize the notion of a string.

Note that when we write $s=x_1\cdots x_k$, this implicitly binds $x_1,\dots ,x_k$ to the individual characters of $s$. Because there are $k$ variables bound in this manner, we know that the string has length $k$.

Unlike strings in a programming language, we explicitly define the set of possible characters that make up our strings. We call this set the alphabet under consideration and denote it with $\Sigma$ ($\text{LATEX}$: \Sigma). Here are some examples of alphabets and possible strings drawn from those alphabets:

In a conventional programming language, we would write the empty string $ϵ$ as "". However, since we traditionally do not use quotes to delineate strings, we must rely on a special symbol to denote the empty string.

Overview of Finite Automata

Now let's look at our first finite automata to get a feel for this sort of abstract machine.

    ┌─────────┬────────┐
    │         a        b
    ↓         │        │
-→ (q0) -a→ (q1) -b→ (q2) -a→ [q3]──┐
   │  ↑                         ↑  a,b
   └b-┘                         └───┘

This simple finite automata recognizes strings drawn from the alphabet $\Sigma =\{a,b\}$. We can think of a finite automata as a labeled, directed graph where the nodes are states and the edges are transitions between states.

Informally, a finite automata operates as follows:

1. The machine begins initially in its start state, denoted in the graph above as the state $q_0$ with an incoming edge but no out-going state.
2. Next it reads in an input string character-by-character. As it reads each character, the machine transitions from its current state to a new state by moving along the edge annotated with the character that was read in.
3. Once the input string is completely consumed, we check to see what state the machine ended on. If the state is an accepting state, then the machine accepts the input string, i.e., returns "true." Otherwise, the machine rejects the input string, i.e., returns "false." In our example, we denote a final state in brackets rather than parentheses, so $q_3$ above is an accepting state whereas all the other states are normal.

As an example, here is how the machine operates over the string $ababa$:

• The machine initially starts in $q_0$.
• The machine reads an $a$ and transitions from $q_0$ to $q_1$.
• The machine reads a $b$ and transitions from $q_1$ to $q_2$.
• The machine reads an $a$ and transitions from $q_2$ to $q_0$.
• The machine reads a $b$ and transitions from $q_0$ back to $q_0$.
• The machine reads an $a$ and transitions from $q_0$ back to $q_1$.

So when reading the string $ababa$, the machine ends on state $q_1$. $q_1$ is not an accepting state, so the automata rejects this string. In contrast, the machine would accept the string $bbababa$.

With some effort, we can also verify that the strings:

• $bbbababbb$,
• $abab$, and
• $aba$,

Are accepted by this automata, whereas the strings

• $bbbb$,
• $aaaa$, and
• The empty string $ϵ$

Are not accepted by this automata.

What are the set of strings that the automata accepts? It turns out that the automata accepts any string that contains $aba$! We can observe this by inspecting the states and transitions of the automata and ask the question: how do we reach the acceptance state $q_3$?

We can only reach this state by moving from $q_0$ through $q_1$ and $q_2$ and finally to $q_3$. According to the transitions, we can only do so by reading in the characters $a$, $b$, and $a$ in order. Also note that:

• If we have not seen $aba$ yet, then any character not involved in this pattern returns us to $q_0$, i.e., our search for this substring resets.
• Once we have seen $aba$ and land in $q_3$, anything that we read keeps us in this acceptance state. In other words, once we reach $q_3$, we will always accept the string!

Finite Automata Formally Defined

Now that we have a high-level idea of how finite automata operate, let's look at their formal description.

Note that even though the automata is a directed graph, we do not model it directly as such! Instead, we model it as a collection of five components---the set of states, alphabet, initial state, transition function, and accepting states. The graph-like nature of an automata is inferred by this choice of representation:

• States are the nodes.
• The transition function contains the (directed) edges.

In particular, note that the transition function, when viewed as a relation, can be thought of a set of pairs, just like the edges of a graph!

Our example automata from above can be formally represented as follows:

• $Q=\{q_0,q_1,q_2,q_3\}$.
• $\Sigma =\{a,b\}$.
• $q_0$ is the initial state.
• $F=\{q_3\}$.

The transition function is defined by the following transition pairs expressed in a state transition table:

For example, in state $q_0$, if the automata reads an $a$, then the automata transitions to state $q_1$.

Acceptance

In order to formally verify that an automata is correct, we also need to formalize the notion of acceptance. Acceptance has a somewhat complicated definition; let's take a look:

Intuitively, this definition says that an automata accepts a string if the string drives the automata from its starting state to a final state.