CSCI 341 Theory of Computation

Fall 2025, with Schmid

Automata

Last time, we saw that state diagrams were useful as compact representations of some top-down puzzle games like Sokoban and mazes. Our definition of "state diagram" was a bit informal, but that was actually for good reason: they are supposed to be useful pictures, not mathematical objects per-se. This section is about the formal definition of automaton and its consequences (first introduced by Stephen Cole Kleene in the 1950s while working at the RAND corporation).

What do you mean by formal? Well, I'm so glad you asked. A formal definition is really a precise, unambiguous description (as in it cannot be interpreted in more than one way) of a mathematical object. The data of a formal definition consists of all of the components of the object it is defining. In our case, the mathematical object in question is a mathematical model of a computer called an automaton, and the data of the definition is contained in the bullet points below it.

(Automaton) An automaton \(\mathcal A = (Q, A, \delta, F)\) consists of the following four pieces of information:
  • A set \(Q\) of states, called the state space
  • A finite set \(A\) of input letters, called the input alphabet
  • A set \(\delta \subseteq Q \times A \times Q\) of transitions, called the transition relation
  • A set \(F \subseteq Q\) of final (also called accepting) states
Given states \(x_1,x_2 \in Q\) and an input letter \(a \in A\), we write \(x_1 \xrightarrow{a}_\delta x_2\) to mean that \((s_1, a, s_2) \in \delta\). Furthermore, given \(x \in Q\) and an input letter \(a \in A\), we define the set of outgoing \(a\)-transitions from state \(x\) by \[ \delta(x, a) = \{y \in Q \mid x \xrightarrow{a}_\delta y\} \] What this notation means is that a state \(y \in Q\) is in \(\delta(x, a)\) precisely when \(x \xrightarrow{a}_\delta y\). If \(\delta\) is clear from context, we'll usually write \(\xrightarrow{a}\) instead of \(\xrightarrow{a}_\delta\).

Recall that a relation is a set of tuples, which are immutable finite lists (just like in Python). In the definition of automaton, the transition relation is a ternary relation, which means it consists of a set of triples \((x, a, y)\), immutable lists of length \(3\). Every automaton can be drawn visually using a state diagram, just like the ones we drew in the previous section.

(Abstract State Diagram (A) again) Recall this example from last time:
Abstract state diagram (A)
Abstract state diagram (A) is a visual depiction of the automaton \(\mathcal A = (Q, A, \delta, F)\), where \[ \begin{aligned} Q &= \{s_1, s_2, s_3, s_4\} \\ A &= \{\Uparrow, \Rightarrow, \Downarrow, \Leftarrow\} \\ \delta &= \{ (s_1, \Rightarrow, s_2), (s_2, \Leftarrow, s_4), (s_2, \Uparrow, s_3), (s_3, \Downarrow, s_2), (s_4, \Rightarrow, s_2) \} \\ F &= \{s_2, s_3, s_4\} \end{aligned} \] Here, we have taken the final states of \(\mathcal A\) to be the winning states. The double-outline indicates that the state is an accepting state.

Just like with understanding any mathematical definition, it is important to start by considering its most trivial examples.

(Empty) The empty automaton \(\mathcal A_\emptyset = (Q, A, \delta, F)\) has \[ Q = \delta = F = \emptyset \]
(Sink) The sink automaton \(\mathcal A_\bullet = (Q, A, \delta, F)\) has \[ Q = \{\bullet\} \qquad \delta = F = \emptyset \]
(Diverging Loop) The diverging loop automaton \(\mathcal A_\circlearrowright = (Q, A, \delta, F)\) has \[ Q = \{\bullet\} \qquad \delta = \{(\bullet, a, \bullet) \mid a \in A\} \qquad F = \emptyset \]
(All-Accepting) The all-accepting automaton \(\mathcal A_\checkmark = (Q, A, \delta, F)\) has \[ Q = \{\bullet\} \qquad \delta = \{(\bullet, a, \bullet) \mid a \in A\} \qquad F = Q \]
(Simple Diagrams) Draw state diagrams for the Empty, Sink, Diverging Loop, and All-Accepting automata when \(A = \{0, 1\}\).

Just like before, an easy way to write down the transition relation of an automaton is using its transition table.

(Transition Table) Given an automaton \(\mathcal A = (Q, A, \delta, F)\), the transition table for \(\mathcal A\) is a 2-dimensional table where
  • Each row of the table corresponds to a state \(x \in Q\)
  • The first column of the table records whether the row's state is accepting (\(=1\)) or not accepting (\(=0\))
  • All columns but the first colum correspond to an input letter
  • In the column corresponding to \(a\) and row corresponding to \(x\), we record the outgoing \(a\)-transitions from \(x\)
\(\to\) \(F\) \(\cdots\) \(a\)
\(\vdots\) \(\vdots\) \(\vdots\)
\(x\) 1 or 0 \(\cdots\) \(\delta(x, a)\)

Transition tables allow us to go back and forth between state diagrams and automata.

(Transition Table for State Diagram (A)) We've already seen the transition table for diagram (A), but we left out the accepting states part before.
\(\textcolor{gray}{\rightarrow}\) \(F\) \(\Uparrow\) \(\Rightarrow\) \(\Downarrow\) \(\Leftarrow\)
\(s_1\) 0 \(s_2\)
\(s_2\) 1 \(s_3\) \(s_4\)
\(s_3\) 1 \(s_2\)
\(s_4\) 1 \(s_2\)
The transition table for abstract state diagram (A).
(Trivial Tables) Draw transition tables for the empty, sink, diverging loop, and all-accepting automata when \(A = \{0, 1\}\).
(Formalizing) Draw transition tables for the automata below. Use your transition table to write down \(Q\), \(\delta\), and \(F\) for each automaton \(\mathcal A = (Q, A, \delta, F)\) below. Note that the alphabet \(A\) is different from automaton to automaton, so the columns will be different each time.

One thing that we have not addressed at this point is that the definition of automaton that we have given above has a particular feature that games don't really have: a state can have multiple outgoing transitions labelled with the same input letter. When you encounter this kind of situation, you are going to have to write multiple state names into the corresponding item in the transition table.

(Nondeterminism and Transition Tables) Determine the state space \(Q\), the input alphabet \(A\), and the accepting states \(F\) of the automaton below given its transition table. Draw a state diagram of the automaton.

The way you want to interpret this multiple-out-going-transitions situation is that the automaton "runs each outgoing transition in parallel". This kind of branching-into-threads is called nondeterminism.

Partial, Total, Deterministic, and Nondeterministic Automata

As we stated before, the puzzle game examples of automata have the property that each legal action transports you to at most one state. This is a special property of automata that will come up often throughout the course.

(Types of Automata) Let \(\mathcal A = (Q, A, \delta, F)\) be an automaton.
  • \(\mathcal A\) is called deterministic if for any state \(x \in Q\) and any input letter \(a \in A\), \(\delta(x, a)\) has one or fewer elements. If \(\mathcal A\) is not deterministic, it is called nondeterministic.
  • \(\mathcal A\) is called total if for any state \(x \in Q\) and any input letter \(a \in A\), \(\delta(x, a)\) has at least one element. If \(\mathcal A\) is not total, we say that it is partial.
(Differentiating Types) Fix an input alphabet \(A = \{a, b, c\}\). Draw one example of each of the following types of automata \(\mathcal A = (Q, A, \delta, F)\) and write down their transition tables.
  1. \(\mathcal A\) is deterministic and total
  2. \(\mathcal A\) is nondeterministic and total
  3. \(\mathcal A\) is nondeterministic and partial
  4. \(\mathcal A\) is deterministic and partial
(Noticing Patterns) Describe the transition tables for nondeterministic, deterministic, partial, and total automata. In particular: which of these types of automata have
  1. More than one entry in each row/column?
  2. Exactly one entry in each row/column?
  3. Less than one entry in each row/column?
Justify your answers to these questions by making reference to the definition of each property.

Remember from your discrete math course that a function \(f \colon X \to Y\) between two sets \(X\) and \(Y\) is a binary relation \(f \subseteq X \times Y\) such that for any \(x \in X\), there is a unique (i.e., exactly one) \(y \in Y\) such that \((x, y) \in f\). And notationally, if \(f\) is a function and \((x,y) \in f\), then you can write \(f(x) = y\).

(Functional Determinism) Let \(\mathcal A = (Q, A, \delta, F)\) be an automaton. Prove that \(\mathcal A\) is a deterministic and total if and only if \(\delta\) is a function \(\delta \colon Q \times A \to Q\).
Remember how to prove "A if and only if B" statements: first, assume that A is true, and then argue that B follows from A (this called the forward direction). Second, assume that B is true, and then argue that A follows from B (this is called the backwards diection). In this case, "A" is the statement, "\(\mathcal A\) is a total deterministic automaton", and "B" is the statement, "\(\delta\) is a function from \(Q \times A\) to \(Q\)".
If it helps, let \(X = Q \times A\) and \(Y = Q\) and show that \(\delta \colon X \to Y\) is a function if and only if \(\mathcal A\) is deterministic and total.

Note. Just to be clear: in the literature, "nondeterministic" usually means "not necessarily deterministic". Technically speaking, with the usual definition of "nondeterministic", every automaton is nondeterministic. There is a reason for this, but that reason is beyond the scope of the course. For us, "nondeterministic" means that some state has more than one outgoing transition.

Top