CSCI 341 Theory of Computation

Fall 2025, with Schmid

Finitely Recognizable Languages

Brzozowski's Fixed Point Theorem tells us that every language is accepted by some state of some automaton. In particular, the language \(L\) is accepted by the state \(L\) in the Brzozowski automaton \(\mathcal A_{Brz}\). One issue with this theorem is that it doesn't tell you how big that automaton might be. In fact, it could be infinite for all we know!

Thankfully, the whole Brzozowski automaton is not needed, only the part that corresponds to \(L\).

Reachability and Local Finiteness

The Brzozowski automaton was most definitely an infinite automaton. But something very special happened in the Unravelling a Language problem: the states reachable from that language were finite in number.

(Generated, Locally Finite) Let \(\mathcal A = (Q, A, \delta, F)\) be an automaton and let \(x \in Q\) be a state. The automaton generated by \(x\) is the automaton \(\langle x \rangle_{\mathcal A} = (Q_x, A, \delta_x, F_x)\) defined by \[\begin{aligned} Q_x &= \bigcup_{w \in A^*} \delta(x, w) \\ \delta_x &= \delta \cap (Q_x \times Q_x) \\ F_x &= F \cap Q_x \\ \end{aligned}\] The state \(x \in Q\) of \(\mathcal A\) is called locally finite if \(Q_x\) is finite, i.e., \(\langle x \rangle_{\mathcal A}\) is a finite automaton. The automaton \(\mathcal A\) is called locally finite if every state \(x \in Q\) is locally finite.

Above, the notation \(\bigcup_{w \in A^*} \delta(x, w)\) is shorthand notation for the set \[ \bigcup_{w \in A^*} \delta(x, w) = \{y \mid \text{there is a word \(w \in A^*\) such that \(y \in \delta(x, w)\)}\} \] The definition of \(\delta_x\) just says that it has all the same transitions as \(\delta\) but restricted to \(Q_x\). Note that \(\langle x \rangle_{\mathcal A}\) has the same alphabet as \(\mathcal A\).

(A=B) Recall that in the Brzozowski automaton \(\mathcal A_{Brz}\), the states are languages, the transitions are given by derivatives, \(L \xrightarrow{a} a^{-1}L\), and the accepting states are the languages \(L\subseteq A^*\) that contain the empty word \(\varepsilon \in L\). The following language is a classic example of a language that generates an infinite subautomaton of the Brzozowski automaton \(\mathcal A_{Brz}\): \[ L_{a=b} = \big\{ a^nb^n \mid n \in \mathbb N\big\} \] After \(k\) \(a\)-derivatives, the language becomes \[ a^{-k}L_{a=b} = \big\{ a^{n-k}b^n \mid n \in \mathbb N, n \ge k\big\} \] If \(k \lneq k'\), then \(a^{-k}L_{a=b} \neq a^{-k'}L_{a=b}\), so there is a distinct state in \(\langle L_{a=b}\rangle_{\mathcal A_{Brz}}\) for each \(k \in \mathbb N\). This means infinitely many!

(Distinct Derivatives of A=B) Show that \(a^{-1}L_{a=b} \neq a^{-2}L_{a=b}\) by finding a word in one of the languages that is not in the other. How would you generalize this to a proof that if \(k \lneq k'\), then \(a^{-k}L_{a=b} \neq a^{-k'}L_{a=b}\)?

It turns out that \(L_{a=b}\) is not accepted by any state in any finite automaton. We don't quite have the tools to prove this yet, though. We will see those later when we talk about the Pumping Lemma for finite automata.

(Reachable = Generated) Let \(\mathcal A = (Q, A, \delta, F)\) be an automaton and let \(x \in Q\) be a state. Convince yourself of the following three statements:

\(Q_x = \{ y \in Q \mid \text{there is a path \(x \xrightarrow{a_1} x_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} y\) in \(\mathcal A\)} \}\)
for any \(y,z \in Q_x\), \(y \xrightarrow{a} z\) in \(\mathcal A\) if and only if \(y \xrightarrow{a} z\) in \(\langle x \rangle_{\mathcal A}\)
for any \(y \in Q_x\), \(y\in F\) if and only if \(y \in F_x\)

Explain why this implies that \(\mathcal L(\mathcal A, x) = \mathcal L(\langle x \rangle_{\mathcal A}, x)\).

Remember that to prove a statement like "\(P\) if and only if \(Q\)", you need to write two separate proofs: you need to prove (1) that "if \(P\), then \(Q\)", and (2) that "if \(Q\), then \(P\)".

(Reverse Naturals Again) Remember that the Reverse Naturals automaton was defined by \(Q = \mathbb N\), \(A = \{l\}\), and \(n + 1 \xrightarrow{l} n\) for all \(n \in Q\). Is the Reverse Naturals automaton locally finite? What if we replace \(l\) with the the input letter \(s\) that adds one instead of subtracts: \(n \xrightarrow{s} n + 1\)?

Finitely Recognizable Languages

So we've seen that it's possible for a language to generate an infinite automaton. Which ones are the languages that generate finite automata? Obviously, we can't store an infinite automaton in a computer, let alone run one. Which languages can be accepted by a state in a finite automaton? In fact, which languages can be accepted by a state in a deterministic, or total deterministic finite automaton? Questions like this lead us to considering a whole range of different families of languages in this course.

(Language Families, Finitely Recognizable) A family of languages is a set of languages \(\mathsf{Fam} \subseteq 2^{A^*}\) over a fixed alphabet of input letters \(A\). We are concerned with the following families of languages:

A language \(L\subseteq A^*\) is finitely recognizable if there is a finite automaton \(\mathcal A = (Q, A, \delta, F)\) (i.e., \(Q\) is finite) and a state \(x \in Q\) such that \(L = \mathcal L(\mathcal A, x)\). The family of finitely recognizable languages is \[ \mathsf{Fin} = \big\{ L \subseteq A^* \mid \text{\(L\) is finitely recognizable} \big\} \]
A language \(L\subseteq A^*\) is deterministic finitely recognizable if there is a deterministic finite automaton \(\mathcal A = (Q, A, \delta, F)\) and a state \(x \in Q\) such that \(L = \mathcal L(\mathcal A, x)\). The family of deterministic finitely recognizable languages is \[ \mathsf{DFin} = \big\{ L \subseteq A^* \mid \text{\(L\) is deterministic finitely recognizable} \big\} \]
A language \(L\subseteq A^*\) is total deterministic finitely recognizable if there is a total deterministic finite automaton \(\mathcal A = (Q, A, \delta, F)\) and a state \(x \in Q\) such that \(L = \mathcal L(\mathcal A, x)\). The family of total deterministic finitely recognizable languages is \[ \mathsf{TDFin} = \big\{ L \subseteq A^* \mid \text{\(L\) is total deterministic finitely recognizable} \big\} \]

Something you should notice immediately: every total deterministic automaton is a deterministic automaton, and every deterministic automaton is an automaton. This means implies that \[ \mathsf{TDFin} \subseteq \mathsf{DFin} \subseteq \mathsf{Fin} \] right off the bat! But what about the reverse inclusions?

(CJ's Pergatory) For each of the deterministic partial automata below, find a total deterministic automaton with a state that accepts the same language as \(x\). In each example, the input alphabet is \(A = \{a, b, c\}\).

(1)

(2)

(3)

(4)

You only ever need to add one state!

(Total vs Partial) Prove that \(\mathsf{DFin} = \mathsf{TDFin}\) by describing how to turn a deterministic automaton into a total deterministic automaton without changing the languages accepted by the states.

What did you do in the CJ's Pergatory exercise every time?

In the next lecture, we are going to see that in fact, all three families of languages are equal.

Top