Formal Languages

Overview

Formal languages. We fix a finite alphabet $\Sigma$ (for example $\{0,1\}$). A word is a finite sequence of symbols from $\Sigma$, and a language is a set of words. The central question: how to describe and recognize a language? Two complementary tools are available. Regular expressions describe languages through formulas (union, concatenation, Kleene star). Finite automata recognize them via a computation mechanism: one reads the word letter by letter, changing state, and accepts or rejects based on the final state.

Deterministic and nondeterministic automata. A deterministic automaton (DFA) has exactly one transition per symbol from each state: the computation is entirely determined by the word. A nondeterministic automaton (NFA) allows multiple possible transitions (or none) and accepts if there exists at least one path leading to an accepting state. One can also add $\varepsilon$-transitions: spontaneous transitions that consume no symbol. Despite this extra flexibility, NFAs recognize exactly the same languages as DFAs.

Regular languages and their limits. The languages recognized by finite automata are called regular languages. Kleene's theorem shows that these are exactly those described by regular expressions. Regular languages are closed under union, concatenation, Kleene star, intersection, and complement. But they have limits: the pumping lemma provides a criterion to prove that a language is not regular. For example, $\{a^n b^n : n \geq 0\}$ escapes finite automata because it would require memorizing an arbitrary number of $a$'s.

Minimality. The Myhill-Nerode theorem characterizes regular languages via an algebraic condition (finitely many equivalence classes) and shows that every regular language has a unique minimal DFA. It can be effectively constructed.

Course

Words and languages

Definition (Alphabet, word, language). An alphabet is a finite nonempty set $\Sigma$. A word over $\Sigma$ is a finite sequence $w = a_1 a_2 \cdots a_n$ with $a_i \in \Sigma$. The integer $n$ is the length of $w$, denoted $|w|$. The empty word, denoted $\varepsilon$, is the unique word of length $0$. We write $\Sigma^*$ for the set of all words over $\Sigma$. A language over $\Sigma$ is a subset $L \subseteq \Sigma^*$.

Definition (Concatenation). The concatenation of two words $u = a_1 \cdots a_m$ and $v = b_1 \cdots b_n$ is the word $uv = a_1 \cdots a_m b_1 \cdots b_n$. This operation is associative, with identity element $\varepsilon$. The monoid $(\Sigma^*, \cdot, \varepsilon)$ is the free monoid on $\Sigma$.

Definition (Operations on languages). Let $L, L' \subseteq \Sigma^*$.

Deterministic finite automata

A finite automaton reads a word once, from left to right, and keeps nothing from one letter to the next except its current state. Everything it will still use about the prefix already read is therefore compressed into one of finitely many states.

Definition (Deterministic finite automaton). A deterministic finite automaton (DFA) is a quintuple $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ where: $Q$ is a finite set of states, $\Sigma$ is an alphabet, $\delta : Q \times \Sigma \to Q$ is the transition function, $q_0 \in Q$ is the initial state, $F \subseteq Q$ is the set of accepting states.

Definition (Extended transition function, recognized language). We extend $\delta$ to $Q \times \Sigma^*$ by: $\hat{\delta}(q, \varepsilon) = q$ and $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$. A word $w$ is accepted by $\mathcal{A}$ if $\hat{\delta}(q_0, w) \in F$. The recognized language of $\mathcal{A}$ is $L(\mathcal{A}) = \{w \in \Sigma^* : \hat{\delta}(q_0, w) \in F\}$.

Definition (Regular language). A language $L \subseteq \Sigma^*$ is regular if there exists a DFA $\mathcal{A}$ such that $L = L(\mathcal{A})$.

Example. Over $\Sigma = \{0,1\}$, the language of words containing an even number of $1$'s is recognized by the DFA with two states $Q = \{q_0, q_1\}$, $F = \{q_0\}$, $\delta(q_0, 0) = q_0$, $\delta(q_0, 1) = q_1$, $\delta(q_1, 0) = q_1$, $\delta(q_1, 1) = q_0$. The current state stores the parity of the number of $1$'s read so far.

q0 q1 1 1 0 0
The automaton of the example, drawn with the conventions used throughout: a circle is a state, a double circle an accepting state, the incoming stub marks the initial state, and an arrow labelled $a$ is a transition on $a$. Reading a $0$ keeps the state and reading a $1$ crosses, so the state reached by a word is the parity of its number of $1$'s.

Nondeterministic finite automata

Definition (Nondeterministic finite automaton). A nondeterministic finite automaton (NFA) is a quintuple $\mathcal{A} = (Q, \Sigma, \Delta, I, F)$ where: $Q$ is a finite set of states, $\Sigma$ is an alphabet, $\Delta \subseteq Q \times \Sigma \times Q$ is the transition relation, $I \subseteq Q$ is the set of initial states, $F \subseteq Q$ is the set of accepting states. Equivalently, one can view $\Delta$ as a function $\delta : Q \times \Sigma \to \mathcal{P}(Q)$. The difference with a DFA: there can be $0$, $1$, or several transitions from a state for the same symbol, and there can be multiple initial states.

Definition (Acceptance by an NFA). We extend $\delta$ to sets of states: for $S \subseteq Q$ and $a \in \Sigma$, $\delta(S, a) = \bigcup_{q \in S} \delta(q, a)$, then to words: $\hat{\delta}(S, \varepsilon) = S$ and $\hat{\delta}(S, wa) = \delta(\hat{\delta}(S, w), a)$. A word $w$ is accepted if $\hat{\delta}(I, w) \cap F \neq \varnothing$. The recognized language is $L(\mathcal{A}) = \{w \in \Sigma^* : \hat{\delta}(I, w) \cap F \neq \varnothing\}$.

Definition (NFA with $\varepsilon$-transitions). An $\varepsilon$-NFA is an NFA where the transition relation is $\Delta \subseteq Q \times (\Sigma \cup \{\varepsilon\}) \times Q$. For $S \subseteq Q$, the $\varepsilon$-closure $\mathrm{Cl}_\varepsilon(S)$ is the smallest set containing $S$ and closed under $\varepsilon$-transitions. Acceptance is defined by taking the $\varepsilon$-closure at each step.

A nondeterministic automaton is not in one state after reading a prefix, but in a set of states. That set is determined by the prefix, and a finite automaton has finitely many sets of states, so the set itself can be used as the state of a deterministic automaton.

Theorem (DFA-NFA equivalence). For every NFA $\mathcal{N}$, there exists a DFA $\mathcal{D}$ such that $L(\mathcal{D}) = L(\mathcal{N})$. More precisely, if $\mathcal{N}$ has $n$ states, $\mathcal{D}$ has at most $2^n$ states.

Proof. Subset construction. Let $\mathcal{N} = (Q, \Sigma, \delta, I, F)$. We build the DFA $\mathcal{D} = (\mathcal{P}(Q), \Sigma, \delta', I, F')$ with $\delta'(S, a) = \bigcup_{q \in S} \delta(q, a)$ and $F' = \{S \in \mathcal{P}(Q) : S \cap F \neq \varnothing\}$. The state set of $\mathcal{D}$ is $\mathcal{P}(Q)$: each DFA state encodes the set of NFA states reachable after reading a given prefix. We show by induction on $|w|$ that $\hat{\delta}'(I, w) = \hat{\delta}(I, w)$, where $\hat{\delta}'$ denotes the extended transition of $\mathcal{D}$ (with values in $\mathcal{P}(Q)$) and $\hat{\delta}$ the transition of $\mathcal{N}$ extended to subsets of $Q$. Base case. $\hat{\delta}'(I, \varepsilon) = I = \hat{\delta}(I, \varepsilon)$. Inductive step. Let $w = ua$ with $a \in \Sigma$. Setting $S = \hat{\delta}'(I, u) = \hat{\delta}(I, u)$ (induction hypothesis), we get $\hat{\delta}'(I, ua) = \delta'(S, a) = \bigcup_{q \in S} \delta(q, a) = \hat{\delta}(S, a) = \hat{\delta}(I, ua)$. Conclusion. $w \in L(\mathcal{D})$ iff $\hat{\delta}'(I, w) \in F'$ iff $\hat{\delta}(I, w) \cap F \neq \varnothing$ iff $w \in L(\mathcal{N})$.
1 2 a a, b {1} {1, 2} a b b a
Left: an NFA for the words over $\{a,b\}$ ending in $a$. On an $a$ from state $1$ the automaton may stay in $1$ or move to $2$.Right: the DFA produced by the subset construction. Its states are the sets of NFA states reachable by the prefix read, and only two of the four subsets are reachable, so the $2^n$ bound is an upper bound and not a count.

Corollary. $\varepsilon$-NFAs recognize exactly the regular languages.

Proof. We first transform an $\varepsilon$-NFA into an NFA (without $\varepsilon$-transitions): set $\delta'(q, a) = \mathrm{Cl}_\varepsilon(\delta(\mathrm{Cl}_\varepsilon(\{q\}), a))$ and $I' = \mathrm{Cl}_\varepsilon(I)$, then apply the subset construction.

Regular expressions

Definition (Regular expression). Regular expressions over $\Sigma$ are defined inductively: (i) $\varnothing$ is a regular expression (denotes $\varnothing$), (ii) $\varepsilon$ is a regular expression (denotes $\{\varepsilon\}$), (iii) for every $a \in \Sigma$, $a$ is a regular expression (denotes $\{a\}$), (iv) if $r$ and $s$ are regular expressions, then $(r + s)$, $(r \cdot s)$ and $(r^*)$ are also regular expressions, denoting $L(r) \cup L(s)$, $L(r) \cdot L(s)$ and $L(r)^*$ respectively.

An expression is built from smaller expressions and an automaton is built from fewer states, so each direction of the next theorem follows one of these two structures: three gadgets glue automata together for $r+s$, $r \cdot s$ and $r^*$, and states are deleted one at a time to produce an expression.

Theorem (Kleene). A language is regular if and only if it is denoted by a regular expression.

Proof. $(\Leftarrow)$ We show that for every regular expression $r$, $L(r)$ is recognized by an $\varepsilon$-NFA, by structural induction. Base cases. $\varnothing$: one state, no accepting state. $\varepsilon$: one state, both initial and accepting. $a$: two states $q_0, q_1$, one transition $q_0 \xrightarrow{a} q_1$, $q_0$ initial, $q_1$ accepting. Union ($r + s$). Take the $\varepsilon$-NFAs $\mathcal{A}_r$ and $\mathcal{A}_s$ (with disjoint states), add a new initial state $q_0$ with $\varepsilon$-transitions to the initial states of $\mathcal{A}_r$ and $\mathcal{A}_s$. The accepting states are those of $\mathcal{A}_r$ and $\mathcal{A}_s$. Concatenation ($r \cdot s$). Add $\varepsilon$-transitions from each accepting state of $\mathcal{A}_r$ to each initial state of $\mathcal{A}_s$. The initial states are those of $\mathcal{A}_r$, the accepting states are those of $\mathcal{A}_s$. Star ($r^*$). Add a new state $q_0$, initial and accepting, with an $\varepsilon$-transition to each initial state of $\mathcal{A}_r$, and $\varepsilon$-transitions from each accepting state of $\mathcal{A}_r$ to $q_0$. In each case, the resulting $\varepsilon$-NFA recognizes the desired language, so it is regular. $(\Rightarrow)$ We use the state elimination method. Let $\mathcal{A}$ be a DFA with $n$ states. We generalize transition labels to carry regular expressions (a generalized automaton). We eliminate states one by one: when removing a state $q_k$, for every pair $(q_i, q_j)$ of remaining states, we replace the label from $q_i$ to $q_j$ by $r_{ij} + r_{ik} \cdot r_{kk}^* \cdot r_{kj}$, where $r_{ij}$, $r_{ik}$, $r_{kj}$, $r_{kk}$ are the current labels. When only the initial state $q_0$ and an accepting state $q_f$ remain, the resulting regular expression denotes the recognized language. If $F$ contains multiple states, we take the union.
Ar As ε ε Ar As ε Ar ε ε
Left: union. A new initial state with an $\varepsilon$-transition into each of $\mathcal{A}_r$ and $\mathcal{A}_s$, whose accepting states stay accepting.Middle: concatenation. An $\varepsilon$-transition from the accepting state of $\mathcal{A}_r$ to the initial state of $\mathcal{A}_s$. The accepting state of $\mathcal{A}_r$ stops accepting, so the word has to be finished inside $\mathcal{A}_s$.Right: star. A new state, initial and accepting, with an $\varepsilon$-transition into $\mathcal{A}_r$ and one back from it, so $\mathcal{A}_r$ runs any number of times, zero included.
qi qk qj rik rkj rkk rij qi qj rij + rik rkk* rkj
Left: the paths from $q_i$ to $q_j$ before $q_k$ is removed. Such a path either avoids $q_k$, reading a word of $r_{ij}$, or enters $q_k$, goes around its loop any number of times, and leaves, reading a word of $r_{ik} r_{kk}^* r_{kj}$.Right: after removal. The single label is the sum of the two cases, so no path is lost and none is created.

Closure properties

Proposition (Closure under union). If $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is regular.

Proof. By Kleene's theorem, $L_1$ and $L_2$ are denoted by regular expressions $r_1$ and $r_2$. Then $r_1 + r_2$ is a regular expression denoting $L_1 \cup L_2$, which is therefore regular.

Proposition (Closure under complement). If $L$ is regular, then $\Sigma^* \setminus L$ is regular.

Proof. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$. The DFA $(Q, \Sigma, \delta, q_0, Q \setminus F)$ recognizes $\Sigma^* \setminus L$.

Proposition (Closure under intersection). If $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ is regular.

Proof. Idea. Run the two automata on the same word at the same time. A state of the product is a pair, one component per automaton, and each component moves as it would on its own. By De Morgan: $L_1 \cap L_2 = \overline{\bar{L_1} \cup \bar{L_2}}$, and we use closure under complement and union. One can also directly construct the product automaton: if $\mathcal{A}_i = (Q_i, \Sigma, \delta_i, q_{0,i}, F_i)$ for $i = 1,2$, set $\mathcal{A} = (Q_1 \times Q_2, \Sigma, \delta, (q_{0,1}, q_{0,2}), F_1 \times F_2)$ with $\delta((q_1, q_2), a) = (\delta_1(q_1, a), \delta_2(q_2, a))$. Then $\hat{\delta}((q_{0,1}, q_{0,2}), w) = (\hat{\delta}_1(q_{0,1}, w), \hat{\delta}_2(q_{0,2}, w))$ (by immediate induction), so $w \in L(\mathcal{A})$ iff $w \in L_1 \cap L_2$.
(0, 0) (1, 0) (0, 1) (1, 1) a a a a b b b b |w|a even |w|a odd |w|b even |w|b odd
The product of the automaton counting $a$'s modulo $2$ with the automaton counting $b$'s modulo $2$, over $\Sigma = \{a,b\}$. The first component of a state is the state of the first automaton and the second component that of the second, so reading an $a$ moves horizontally and reading a $b$ moves vertically. Accepting the pair $(0,0)$ recognizes the intersection; accepting the two states of the top row would recognize the first language alone.

Proposition (Closure under morphism image and preimage). Let $\varphi : \Sigma^* \to \Gamma^*$ be a monoid morphism. If $L$ is a regular language over $\Gamma$, then $\varphi^{-1}(L)$ is regular over $\Sigma$. If $L$ is a regular language over $\Sigma$, then $\varphi(L)$ is regular over $\Gamma$.

Proof. For $\varphi^{-1}(L)$: let $(Q, \Gamma, \delta, q_0, F)$ be a DFA for $L$. We build the DFA $(Q, \Sigma, \delta', q_0, F)$ with $\delta'(q, a) = \hat{\delta}(q, \varphi(a))$. Then $\hat{\delta}'(q_0, w) = \hat{\delta}(q_0, \varphi(w))$ (by induction on $|w|$), so $L(\mathcal{A}') = \varphi^{-1}(L)$. For $\varphi(L)$: let $r$ be a regular expression for $L$. Replace each letter $a$ by $\varphi(a)$ in $r$. The resulting expression denotes $\varphi(L)$.

Pumping lemma

A DFA has finitely many states, so a run on a word longer than the number of states visits some state twice. The piece of the word read between the two visits leads from that state back to itself, so it can be read again, or skipped, and the run still ends where it did.

Theorem (Pumping Lemma). Let $L$ be a regular language. There exists an integer $p \geq 1$ (the pumping length) such that every word $w \in L$ with $|w| \geq p$ can be decomposed as $w = xyz$ with: (i) $|y| \geq 1$, (ii) $|xy| \leq p$, (iii) $\forall k \geq 0,\; xy^k z \in L$.

Proof. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$, and $p = |Q|$. Let $w = a_1 \cdots a_n \in L$ with $n \geq p$. Reading $w$ visits states $r_0 = q_0, r_1, \ldots, r_n$ with $r_i = \hat{\delta}(q_0, a_1 \cdots a_i)$. Among the first $p+1$ states $r_0, r_1, \ldots, r_p$, there are $|Q| = p$ possible states, so by the pigeonhole principle, there exist $0 \leq i < j \leq p$ such that $r_i = r_j$. Set $x = a_1 \cdots a_i$, $y = a_{i+1} \cdots a_j$, $z = a_{j+1} \cdots a_n$. Then $|y| = j - i \geq 1$, $|xy| = j \leq p$, and for all $k \geq 0$: reading $xy^k z$ starts from $q_0$, reaches $r_i$ after $x$, loops $k$ times on the cycle $r_i \to \cdots \to r_j = r_i$ by reading $y^k$, then reaches $r_n$ after $z$. Since $r_n \in F$, we have $xy^k z \in L$.
y r0 ri = rj rn x z
The run of a word $w \in L$ with $|w| \geq p$ in a DFA with $p$ states. Its first $p+1$ states cannot all be distinct, so the run comes back to a state it has already visited, within the first $p$ letters. The letters read around that loop form $y$, and going around it $k$ times reads $xy^kz$ and ends in $r_n$, which is accepting. The two conditions of the lemma are read off the picture: $y$ is nonempty because a loop has at least one edge, and $|xy| \leq p$ because the repetition occurs among the first $p+1$ states.

Myhill-Nerode theorem and minimal automaton

Definition (Nerode congruence). Let $L \subseteq \Sigma^*$. The Nerode congruence of $L$ is the relation $\sim_L$ defined on $\Sigma^*$ by: $u \sim_L v$ if and only if $\forall w \in \Sigma^*,\; (uw \in L \iff vw \in L)$.

Proposition. The relation $\sim_L$ is an equivalence relation on $\Sigma^*$, right-compatible with concatenation: if $u \sim_L v$, then for all $a \in \Sigma$, $ua \sim_L va$.

Proof. Reflexivity, symmetry, and transitivity are immediate. For compatibility: if $u \sim_L v$, then for all $a \in \Sigma$ and all $w \in \Sigma^*$, $uaw \in L \iff vaw \in L$ (taking $aw$ as suffix in the definition), so $ua \sim_L va$.

Theorem (Myhill-Nerode). Let $L \subseteq \Sigma^*$. The following are equivalent: (1) $L$ is regular. (2) $\sim_L$ has finitely many equivalence classes. Moreover, the number of classes of $\sim_L$ is exactly the number of states of the smallest DFA recognizing $L$.

Proof. Idea. Take the words themselves as states. An automaton for $L$ may send $u$ and $v$ to the same state only if no suffix distinguishes them, so the classes of $\sim_L$ are the states of every automaton for $L$, merged as much as they can be. $(1 \Rightarrow 2)$. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$. Define $\equiv_\mathcal{A}$ by $u \equiv_\mathcal{A} v$ iff $\hat{\delta}(q_0, u) = \hat{\delta}(q_0, v)$. If $u \equiv_\mathcal{A} v$, then for all $w$, $\hat{\delta}(q_0, uw) = \hat{\delta}(\hat{\delta}(q_0, u), w) = \hat{\delta}(\hat{\delta}(q_0, v), w) = \hat{\delta}(q_0, vw)$, so $uw \in L \iff vw \in L$, giving $u \sim_L v$. Thus $\equiv_\mathcal{A}$ refines $\sim_L$, and $\sim_L$ has at most $|Q|$ classes. $(2 \Rightarrow 1)$. Suppose $\sim_L$ has finitely many $n$ classes. We build the DFA $\mathcal{A}_L = (Q_L, \Sigma, \delta_L, [\varepsilon], F_L)$ with $Q_L = \Sigma^* / {\sim_L}$ (the set of classes), $\delta_L([u], a) = [ua]$ (well-defined by right compatibility), $[\varepsilon]$ as initial state, and $F_L = \{[u] : u \in L\}$ (well-defined since $u \sim_L v$ and $u \in L$ implies $v \in L$ by taking $w = \varepsilon$). We verify $\hat{\delta}_L([\varepsilon], w) = [w]$ by induction on $|w|$ (base: $\hat{\delta}_L([\varepsilon], \varepsilon) = [\varepsilon]$; step: $\hat{\delta}_L([\varepsilon], wa) = \delta_L([w], a) = [wa]$). So $w \in L(\mathcal{A}_L)$ iff $[w] \in F_L$ iff $w \in L$. Minimality. We saw that for any DFA $\mathcal{A}$ recognizing $L$, $\equiv_\mathcal{A}$ refines $\sim_L$, so $|Q| \geq n$. Since $\mathcal{A}_L$ has exactly $n$ states, $\mathcal{A}_L$ is a DFA of minimal size. Uniqueness. If $\mathcal{A}$ is a DFA recognizing $L$ with $n$ states, then $\equiv_\mathcal{A}$ has exactly $n$ classes and refines $\sim_L$ which also has $n$, so $\equiv_\mathcal{A}$ and $\sim_L$ coincide. The map $\hat{\delta}(q_0, u) \mapsto [u]$ is an isomorphism between $\mathcal{A}$ and $\mathcal{A}_L$ (if all states of $\mathcal{A}$ are reachable).
[ε] ε, b, bb bbb, bbbb [a] a, ab, ba bab, bbab [aa] aa, aba, aab baaba, abab a a b b a, b
The classes of $\sim_L$ for $L$ the words over $\{a,b\}$ containing at least two $a$'s, with a few members of each written out. Two words in the same box are sent into $L$ by exactly the same suffixes, appending a letter sends a whole box into a single box, and $[aa]$ is the box contained in $L$. The three boxes with these arrows are therefore a DFA for $L$, and no DFA can have fewer states, since two words in different boxes must reach different states.

Corollary. Every regular language has, up to isomorphism, a unique minimal DFA (among DFAs whose states are all reachable). It is the Nerode automaton $\mathcal{A}_L$.

Proposition (Effective construction of the minimal automaton). Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA whose states are all reachable. The minimal automaton is obtained by identifying equivalent states: $q \sim q'$ if $\forall w \in \Sigma^*$, $\hat{\delta}(q, w) \in F \iff \hat{\delta}(q', w) \in F$. This relation is computed by successive refinement: start with the partition $\{F, Q \setminus F\}$ and refine by distinguishing $q$ and $q'$ if there exists $a \in \Sigma$ such that $\delta(q, a)$ and $\delta(q', a)$ are not in the same block. Iterate until stabilization.

Proof. Idea. The relation $\sim$ is defined by all the words $w$ at once, which cannot be tested directly. Testing the words of length at most $k$ gives a partition computable from the partition for $k-1$, and the sequence of partitions stops growing after at most $|Q|$ steps. Define $\sim_k$ by: $q \sim_0 q'$ iff $(q \in F \iff q' \in F)$, and $q \sim_{k+1} q'$ iff $q \sim_k q'$ and $\forall a \in \Sigma,\;\delta(q, a) \sim_k \delta(q', a)$. Clearly ${\sim_{k+1}} \subseteq {\sim_k}$. Since $Q$ is finite, there exists $k_0$ such that ${\sim_{k_0}} = {\sim_{k_0+1}}$. We show that ${\sim_{k_0}} = {\sim}$. The inclusion ${\sim} \subseteq {\sim_k}$ for all $k$ is immediate by induction. For the other direction, if $q \sim_{k_0} q'$, then for all $a$, $\delta(q, a) \sim_{k_0} \delta(q', a)$, so by induction on $|w|$, $\hat{\delta}(q, w) \sim_{k_0} \hat{\delta}(q', w)$ for all $w$, which implies $\hat{\delta}(q, w) \in F \iff \hat{\delta}(q', w) \in F$, so $q \sim q'$. The quotient $Q / {\sim}$ gives the minimal automaton.

Techniques

Technique 1. The state is the whole memory. To build a DFA for a language, find a quantity attached to a prefix that takes finitely many values, determines whether the word read so far is in the language, and whose new value after a letter depends only on its old value and that letter.

Exercise. Show that the language $L = \{w \in \{a,b\}^* : |w|_a \equiv 0 \pmod{3}\}$ is regular.

Solution. We build the DFA $\mathcal{A} = (\{q_0, q_1, q_2\}, \{a,b\}, \delta, q_0, \{q_0\})$ with $\delta(q_i, a) = q_{(i+1) \bmod 3}$ and $\delta(q_i, b) = q_i$. The state $q_i$ means the number of $a$'s read is congruent to $i$ modulo $3$. So $\hat{\delta}(q_0, w) = q_{|w|_a \bmod 3}$, and $w \in L(\mathcal{A})$ iff $|w|_a \equiv 0 \pmod{3}$.

Technique 2. A language obtained from regular languages by union, concatenation, star, complement or intersection is regular, so it never has to be recognized directly. Union, concatenation and star are read off regular expressions, complement and intersection off automata.

Exercise. Let $L$ be a regular language over $\Sigma$. Show that the set of words of $L$ of even length is regular.

Solution. Write $\Sigma = \{a_1, \ldots, a_k\}$ and $r = a_1 + \cdots + a_k$. The expression $(r \cdot r)^*$ denotes the words of even length, so that language is regular. The set asked for is its intersection with $L$, and regular languages are closed under intersection.

Technique 3. To prove that $L$ is not regular, assume a pumping length $p$ and rule out every decomposition the lemma allows. The word $w \in L$ with $|w| \geq p$ is yours to choose and the decomposition is not, so choose $w$ so that $|xy| \leq p$ forces $y$ to sit inside one block of letters.

Exercise. Show that $L = \{a^n b^n : n \geq 0\}$ is not regular.

Solution. Suppose for contradiction that $L$ is regular, with pumping length $p$. The word $w = a^p b^p \in L$ satisfies $|w| = 2p \geq p$. By the lemma, $w = xyz$ with $|y| \geq 1$, $|xy| \leq p$. Since $|xy| \leq p$, $x$ and $y$ consist only of $a$'s, so $y = a^m$ with $m \geq 1$. Then $xy^0 z = xz = a^{p-m} b^p \notin L$ since $p - m \neq p$. Contradiction.

Technique 4. To determinize an NFA, take as states the sets of states of the NFA, starting from the set of initial states and keeping only the sets actually reached. A set is accepting as soon as it meets $F$.

Exercise. Determinize the NFA over $\Sigma = \{a,b\}$ with states $\{1,2,3\}$, $I = \{1\}$, $F = \{3\}$ and transitions $\delta(1,a) = \{1,2\}$, $\delta(1,b) = \{1\}$, $\delta(2,a) = \{3\}$, all other transitions empty. Which language does it recognize?

Solution. Starting from $\{1\}$: $\delta'(\{1\},a) = \{1,2\}$ and $\delta'(\{1\},b) = \{1\}$; $\delta'(\{1,2\},a) = \{1,2,3\}$ and $\delta'(\{1,2\},b) = \{1\}$; $\delta'(\{1,2,3\},a) = \{1,2,3\}$ and $\delta'(\{1,2,3\},b) = \{1\}$. Only three of the eight subsets are reached: $\{1\}$, $\{1,2\}$ and $\{1,2,3\}$, the last being the only accepting one since it is the only one meeting $F$. State $2$ is reachable by a word exactly when that word ends with $a$, and state $3$ exactly when it ends with $aa$. The recognized language is therefore $\Sigma^* aa$, the words ending with two $a$'s.

Technique 5. To minimize a DFA whose states are all reachable, start from the partition into accepting and non-accepting states, and split a block whenever some letter sends two of its states into different blocks. Stop when no letter splits anything.

Exercise. Construct the minimal automaton of the DFA over $\Sigma = \{a, b\}$ with five states $\{1, 2, 3, 4, 5\}$, initial state $1$, accepting states $\{1, 4\}$, with $\delta(1, a) = 2$, $\delta(1, b) = 3$, $\delta(2, a) = 4$, $\delta(2, b) = 5$, $\delta(3, a) = 5$, $\delta(3, b) = 4$, $\delta(4, a) = 2$, $\delta(4, b) = 3$, $\delta(5, a) = 3$, $\delta(5, b) = 2$.

Solution. Initial partition: $P_0 = \{A, B\}$ with $A = \{1, 4\}$ (accepting) and $B = \{2, 3, 5\}$. Refinement. For $a$: $\delta(1, a) = 2 \in B$, $\delta(4, a) = 2 \in B$ (identical). For $b$: $\delta(1, b) = 3 \in B$, $\delta(4, b) = 3 \in B$. So $1$ and $4$ stay together. For the states in $B$: $\delta(2, a) = 4 \in A$, $\delta(3, a) = 5 \in B$, $\delta(5, a) = 3 \in B$. So $2$ is distinguished from $3$ and $5$ on $a$. We get $P_1 = \{\{1, 4\}, \{2\}, \{3, 5\}\}$. Check $\{3, 5\}$: $\delta(3, a) = 5 \in \{3,5\}$, $\delta(5, a) = 3 \in \{3,5\}$; $\delta(3, b) = 4 \in \{1,4\}$, $\delta(5, b) = 2 \in \{2\}$. We distinguish $3$ and $5$ on $b$. We get $P_2 = \{\{1, 4\}, \{2\}, \{3\}, \{5\}\}$. Check $\{1, 4\}$: $\delta(1, a) = 2 \in \{2\}$, $\delta(4, a) = 2 \in \{2\}$; $\delta(1, b) = 3 \in \{3\}$, $\delta(4, b) = 3 \in \{3\}$. Stable. So $P_2$ is the final partition. The minimal automaton has $4$ states: $[1] = \{1,4\}$, $[2] = \{2\}$, $[3] = \{3\}$, $[5] = \{5\}$, with initial state $[1]$, accepting state $[1]$, and transitions $\delta([1], a) = [2]$, $\delta([1], b) = [3]$, $\delta([2], a) = [1]$, $\delta([2], b) = [5]$, $\delta([3], a) = [5]$, $\delta([3], b) = [1]$, $\delta([5], a) = [3]$, $\delta([5], b) = [2]$.

Technique 6. To read a regular expression off an automaton, add a new initial state and a new accepting state joined by $\varepsilon$, then delete the other states one at a time, each deletion putting the words that passed through the deleted state into the labels of the surviving edges.

Exercise. Find a regular expression for the language of the DFA over $\Sigma = \{a,b\}$ with states $\{1,2\}$, initial state $1$, accepting state $2$, and $\delta(1,a) = 2$, $\delta(1,b) = 1$, $\delta(2,a) = 2$, $\delta(2,b) = 1$.

Solution. Add an initial state $i$ with $i \xrightarrow{\varepsilon} 1$ and an accepting state $f$ with $2 \xrightarrow{\varepsilon} f$. The current labels are $r_{11} = b$, $r_{12} = a$, $r_{21} = b$, $r_{22} = a$. Deleting $2$. The label from $1$ to $1$ becomes $r_{11} + r_{12} r_{22}^* r_{21} = b + a a^* b$, and the label from $1$ to $f$ becomes $r_{12} r_{22}^* = a a^*$. Deleting $1$. Only $i$ and $f$ remain, joined by $(b + aa^*b)^* a a^*$. Every word of $b + aa^*b$ ends with $b$ and every word of $aa^*$ is a nonempty block of $a$'s, so this is the set of words ending with $a$, also denoted by $(a+b)^*a$.

Technique 7. Two words that no suffix separates must reach the same state. To prove that $L$ is not regular, exhibit an infinite family of words, any two of which are separated by some suffix: they lie in distinct classes of $\sim_L$, so by Myhill-Nerode no finite automaton recognizes $L$.

Exercise. Show that $L = \{a^i b^j : i \neq j\}$ is not regular.

Solution. Consider the words $a^0, a^1, a^2, \ldots$ and let $i < k$. The suffix $b^i$ separates $a^i$ from $a^k$: the word $a^i b^i$ is not in $L$ while $a^k b^i$ is, since $k \neq i$. So $a^i \not\sim_L a^k$ for $i \neq k$, the classes $[a^0], [a^1], [a^2], \ldots$ are pairwise distinct, and $\sim_L$ has infinitely many classes. By Myhill-Nerode, $L$ is not regular.

Exercises

Exercise. Regular languages are closed under the union of two languages, hence of any finite number. Find regular languages whose union is not regular.

Solution. Every singleton $\{w\}$ is regular, being denoted by the expression $w$ itself. Any language $L$ is the union of the singletons $\{w\}$ for $w \in L$, so an arbitrary union of regular languages can be any language at all, $\{a^n b^n : n \geq 0\}$ included. Closure holds for finite unions only: the induction that extends it from two languages to $n$ never reaches an infinite family.

Exercise. The Nerode congruence is compatible with concatenation on the right. Find a language $L$, two words $u \sim_L v$ and a letter $a$ such that $au \not\sim_L av$.

Solution. Take $\Sigma = \{a,b\}$ and $L = \Sigma^* a$, the words ending with $a$. Then $\varepsilon \sim_L b$: for every $w$, both $\varepsilon w = w$ and $bw$ end with $a$ exactly when $w$ does, and neither $\varepsilon$ nor $b$ is in $L$. But $a \varepsilon = a$ belongs to $L$ while $ab$ does not, so the suffix $\varepsilon$ separates them and $a\varepsilon \not\sim_L ab$. A word is read from left to right, so what can still be appended is a suffix. Adding a letter on the right leaves the past untouched and moves both words to the same new class, while adding one on the left rewrites the prefix that has already been read.

Exercise. Every regular language satisfies the conclusion of the pumping lemma. Find a language that satisfies it and is not regular.

Solution. Over $\Sigma = \{a,b,c\}$, take $L = \{c^m a^n b^n : m \geq 1,\ n \geq 0\} \cup \{a,b\}^*$. $L$ satisfies the conclusion with $p = 1$. Let $w \in L$ with $|w| \geq 1$. If $w \in \{a,b\}^*$, write $x = \varepsilon$, $y$ the first letter of $w$ and $z$ the rest: then $|y| = |xy| = 1$ and $xy^kz$ is again a word of $\{a,b\}^*$, so it lies in $L$ for every $k \geq 0$. Otherwise $w = c^m a^n b^n$ with $m \geq 1$; write $x = \varepsilon$, $y = c$ and $z = c^{m-1}a^nb^n$. Then $xy^kz = c^{m-1+k}a^nb^n$, which is in $L$ when $m - 1 + k \geq 1$, and equals $a^nb^n \in \{a,b\}^*$ when $m - 1 + k = 0$. Either way it lies in $L$. $L$ is not regular. If it were, $L \cap c a^* b^*$ would be regular, and that language is $\{c a^n b^n : n \geq 0\}$. Its image under the morphism $\varphi$ defined by $\varphi(c) = \varepsilon$, $\varphi(a) = a$, $\varphi(b) = b$ would then be regular too, but that image is $\{a^n b^n : n \geq 0\}$, which the pumping lemma rules out. The pumping property is therefore necessary for regularity and not sufficient: it can be used to reject a language, never to certify one.

Exercise. Show that $L = \{w \in \{0,1\}^* : w \text{ is a palindrome}\}$ is not regular.

Proof. Let $p$ be the pumping length. The word $w = 0^p 1 0^p \in L$ satisfies $|w| \geq p$. By the lemma, $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$, so $y = 0^m$ with $1 \leq m \leq p$, in the first block of $0$'s. Then $xy^2 z = 0^{p+m} 1 0^p$ is not a palindrome, so $xy^2 z \notin L$. Contradiction.

Exercise. Show that $L = \{0^n 1^n 0^n : n \geq 0\}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$. The word $w = 0^p 1^p 0^p \in L$ satisfies $|w| = 3p \geq p$. By the pumping lemma, $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$, so $y = 0^m$ with $1 \leq m \leq p$ (in the first block). Then $xy^0 z = 0^{p-m} 1^p 0^p \notin L$ since $p - m \neq p$. Contradiction.

Exercise. Show that $L = \{a^{n^2} : n \geq 0\}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$. The word $w = a^{p^2} \in L$ satisfies $|w| = p^2 \geq p$. By the pumping lemma, $w = xyz$ with $|y| = m \geq 1$ and $|xy| \leq p$. Then $|xy^2 z| = p^2 + m$. Since $1 \leq m \leq p$, we have $p^2 < p^2 + m \leq p^2 + p < p^2 + 2p + 1 = (p+1)^2$. So $p^2 + m$ lies strictly between two consecutive perfect squares, hence is not a perfect square, and $xy^2 z \notin L$. Contradiction.

Exercise. Show that $L = \{a^n : n \text{ is prime}\}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$. Let $q$ be a prime $\geq p$. The word $w = a^q \in L$ satisfies $|w| = q \geq p$. By the pumping lemma, $w = xyz$ with $|y| = m \geq 1$, $|xy| \leq p$. Then $|xy^{q+1} z| = q + qm = q(1 + m)$. This is a product of two integers $\geq 2$ ($q$ is prime $\geq 2$ and $1 + m \geq 2$), so it is not prime. Thus $xy^{q+1} z \notin L$, contradiction.

Exercise. Show that $L = \{ww : w \in \{a,b\}^*\}$ is not regular.

Proof. Suppose $L$ is regular with pumping length $p$. The word $w = a^p b a^p b \in L$ satisfies $|w| \geq p$. By the lemma, $w = xyz$ with $|xy| \leq p$, $|y| \geq 1$, so $y = a^m$ ($1 \leq m \leq p$). The word $xy^2 z = a^{p+m} b a^p b$ has length $2p + 2 + m$. If $m$ is odd, this length is odd, so $xy^2 z \notin L$ (every element of $L$ has even length). If $m$ is even, $m = 2\ell$ with $\ell \geq 1$, each half has length $p + 1 + \ell$. Since $p + 1 + \ell \leq p + 2\ell$, the cut falls in the first block of $a$'s. The first half is $a^{p + 1 + \ell}$ (only $a$'s), the second is $a^{\ell - 1} b a^p b$ (contains $b$'s). They differ, so $xy^2 z \notin L$. Contradiction.

Exercise. For a word $w = a_1 \cdots a_n$, we write $w^R = a_n \cdots a_1$ for the mirror word of $w$. Let $L$ be a regular language. Show that $L^R = \{w^R : w \in L\}$ is regular.

Proof. Idea. Reading $w^R$ from left to right is reading $w$ from right to left, so turn every arrow of an automaton for $L$ around. What was determined forwards becomes a guess backwards, which is what nondeterminism is for. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$. We build the NFA $\mathcal{A}^R = (Q, \Sigma, \delta^R, F, \{q_0\})$ by reversing all transitions: $(q', a, q) \in \delta^R$ iff $\delta(q, a) = q'$. The initial states of $\mathcal{A}^R$ are the accepting states of $\mathcal{A}$, and the sole accepting state is $q_0$. We show that $L(\mathcal{A}^R) = L^R$. A word $a_1 \cdots a_n \in L$ iff there exists a path $q_0 \xrightarrow{a_1} r_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} r_n$ in $\mathcal{A}$ with $r_n \in F$. Reversing, $r_n \xrightarrow{a_n} r_{n-1} \xrightarrow{a_{n-1}} \cdots \xrightarrow{a_1} q_0$ is a path in $\mathcal{A}^R$ from $r_n \in F$ (initial state of $\mathcal{A}^R$) to $q_0$ (accepting state of $\mathcal{A}^R$), showing that $a_n \cdots a_1 \in L(\mathcal{A}^R)$. The argument is reversible.

Exercise. Determine the number of classes of the Nerode congruence for $L = \{w \in \{a,b\}^* : w \text{ contains } ab \text{ as a factor}\}$ and deduce the minimal automaton.

Proof. A word $u$ without the factor $ab$ has the form $b^* a^*$ (since after an $a$, every next character must be $a$, otherwise we create a factor $ab$). We distinguish three cases: (1) $u$ contains $ab$ as a factor, (2) $u \in b^* a^+$ (no factor $ab$, ends with $a$), (3) $u \in b^*$ (no factor $ab$, does not end with $a$). Class 1 ($u$ contains $ab$): for all $w \in \Sigma^*$, $uw$ contains $ab$, so $uw \in L$. Class 2 ($u \in b^* a^+$): $u$ ends with $a$, so $uw$ contains $ab$ iff $w$ starts with $b$ or $w$ contains $ab$. That is, $uw \in L \iff w \in b\Sigma^* \cup \Sigma^* ab \Sigma^*$. Class 3 ($u \in b^*$): the concatenation $uw$ does not create a factor $ab$ at the junction (since $u$ ends with $b$ or $u = \varepsilon$), so $uw \in L \iff w$ contains $ab$. The three classes are distinct: with $w = \varepsilon$, class 1 gives $uw \in L$, classes 2 and 3 give $uw \notin L$; with $w = b$, class 2 gives $ub \in L$ (since $u$ ends with $a$), class 3 gives $ub \notin L$. So $\sim_L$ has exactly $3$ classes. The minimal automaton has three states $\{q_0, q_1, q_2\}$: $q_0 = [\varepsilon]$ (class 3), $q_1 = [a]$ (class 2), $q_2 = [ab]$ (class 1). Initial state $q_0$, accepting state $q_2$. Transitions: $\delta(q_0, a) = q_1$, $\delta(q_0, b) = q_0$, $\delta(q_1, a) = q_1$, $\delta(q_1, b) = q_2$, $\delta(q_2, a) = q_2$, $\delta(q_2, b) = q_2$.

Exercise. Let $L$ be a regular language over $\Sigma$ and $M$ an arbitrary language over $\Sigma$. Show that the right quotient $L / M = \{x \in \Sigma^* : \exists y \in M,\; xy \in L\}$ is regular.

Proof. Idea. The automaton for $L$ already reads $x$; all that changes is when to stop. Declare accepting the states from which some word of $M$ still reaches $F$, and the transitions can be left alone. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$. We build the DFA $\mathcal{A}' = (Q, \Sigma, \delta, q_0, F')$ with $F' = \{q \in Q : \exists y \in M,\; \hat{\delta}(q, y) \in F\}$. We only change the set of accepting states. Then $x \in L(\mathcal{A}')$ iff $\hat{\delta}(q_0, x) \in F'$ iff $\exists y \in M,\; \hat{\delta}(\hat{\delta}(q_0, x), y) \in F$ iff $\exists y \in M,\; \hat{\delta}(q_0, xy) \in F$ iff $\exists y \in M,\; xy \in L$ iff $x \in L/M$. So $L(\mathcal{A}') = L/M$, which is regular. Note that $M$ need not be regular. Nothing in the construction says how to decide which states belong to $F'$, and for an arbitrary $M$ nothing can: the automaton exists, and finding it may be impossible.

Exercise (Arden's lemma). Let $A, B \subseteq \Sigma^*$ with $\varepsilon \notin A$. Show that the unique solution of the equation $X = AX \cup B$ is $X = A^* B$. Deduce a method for computing the language recognized by a finite automaton: to each state $q_i$ of a DFA $(Q, \Sigma, \delta, q_0, F)$, associate the language $L_i = \{w \in \Sigma^* : \hat{\delta}(q_i, w) \in F\}$, and solve the resulting system of equations. Apply this method to the DFA over $\Sigma = \{a, b\}$ with three states $\{0, 1, 2\}$, initial state $0$, accepting state $\{0\}$, with $\delta(0, a) = 1$, $\delta(0, b) = 0$, $\delta(1, a) = 2$, $\delta(1, b) = 0$, $\delta(2, a) = 2$, $\delta(2, b) = 2$.

Proof. Verification. $A^* B = A(A^* B) \cup B$ since $A^* = AA^* \cup \{\varepsilon\}$. So $X = A^* B$ is a solution. Uniqueness. Let $X$ be a solution. By iterated substitution: $X = AX \cup B = A(AX \cup B) \cup B = A^2 X \cup AB \cup B$. By induction, $X = A^n X \cup \left(\bigcup_{k=0}^{n-1} A^k\right) B$ for all $n \geq 1$. Since $\varepsilon \notin A$, every word in $A$ has length $\geq 1$, so every word in $A^n$ has length $\geq n$. Let $w \in X$: if $w \in A^n X$ for all $n$, then $|w| \geq n$ for all $n$, which is impossible. So there exists $n$ such that $w \in \left(\bigcup_{k=0}^{n-1} A^k\right) B \subseteq A^* B$. Thus $X \subseteq A^* B$. The reverse inclusion follows from the fact that $A^* B$ is a solution and $X = AX \cup B \supseteq B$, then by induction $X \supseteq A^n B$ for all $n$, so $X \supseteq A^* B$. Application. The system of equations is: $L_i = \bigcup_{a \in \Sigma} a \cdot L_{\delta(i, a)}$, with the term $\cup\;\{\varepsilon\}$ added if $i \in F$. Here: $L_0 = a \cdot L_1 \cup b \cdot L_0 \cup \{\varepsilon\}$, $L_1 = a \cdot L_2 \cup b \cdot L_0$, $L_2 = a \cdot L_2 \cup b \cdot L_2$. By Arden on $L_2$: $L_2 = (a \cup b) L_2 \cup \varnothing$, so $L_2 = (a \cup b)^* \varnothing = \varnothing$. Then $L_1 = b \cdot L_0$. Substituting into $L_0$: $L_0 = ab \cdot L_0 \cup b \cdot L_0 \cup \{\varepsilon\} = (ab \cup b) L_0 \cup \{\varepsilon\}$. By Arden: $L_0 = (ab \cup b)^*$.

Exercise. The subset construction turns an $n$-state NFA into a DFA with at most $2^n$ states. Show that this bound is reached: for every $n \geq 1$, exhibit a language recognized by an NFA with $n+1$ states whose minimal DFA has exactly $2^n$ states.

Proof. Over $\Sigma = \{a,b\}$, let $L_n$ be the set of words whose $n$-th letter from the end is an $a$, that is $L_n = \Sigma^* a \Sigma^{n-1}$. An NFA with $n+1$ states. Take $Q = \{0, 1, \ldots, n\}$, $I = \{0\}$, $F = \{n\}$, with $\delta(0, a) = \{0, 1\}$, $\delta(0, b) = \{0\}$, and $\delta(i, a) = \delta(i, b) = \{i+1\}$ for $1 \leq i \leq n-1$. State $0$ reads the word and guesses at some point that the $a$ it is reading is the one in position $n$ from the end; the states $1, \ldots, n$ then count the $n-1$ letters that must follow. Every DFA needs $2^n$ states. Let $u \neq v$ be two words of length $n$, differing at position $i$ counted from the left, say $u_i = a$ and $v_i = b$. Take $s = b^{i-1}$. The word $us$ has length $n + i - 1$, so its $n$-th letter from the end is its letter in position $i$, namely $u_i = a$; hence $us \in L_n$. The same computation gives $vs \notin L_n$. So $u \not\sim_{L_n} v$: the $2^n$ words of length $n$ are pairwise inequivalent, and by Myhill-Nerode the minimal DFA has at least $2^n$ states. And $2^n$ suffice. Whether $w \in L_n$ depends only on the last $n$ letters of $b^n w$, so the DFA whose states are the $2^n$ words of length $n$, with initial state $b^n$, transition $\delta(x_1 \cdots x_n, c) = x_2 \cdots x_n c$ and accepting states those beginning with $a$, recognizes $L_n$. Its minimal DFA therefore has exactly $2^n$ states.

Exercise. Let $L$ be a regular language over $\Sigma$. Show that $\sqrt{L} = \{w \in \Sigma^* : ww \in L\}$ is regular.

Proof. Idea. An automaton reading $w$ once cannot run the second copy of $w$, since it does not know yet where that copy starts. So it runs the second copy from every state at once: the state to carry is the function sending each possible starting state to the state reached, and a function on a finite set is itself a finite amount of memory. Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA recognizing $L$ with $n = |Q|$. We build a DFA whose states encode both the progress of the first copy of $w$ and the effect of the second copy on every possible state. Set $Q' = Q \times Q^Q$ where $Q^Q$ is the set of functions from $Q$ to $Q$. A state $(q, f)$ means: the first copy has reached state $q$, and for each hypothetical starting state $s$, the second copy would have reached state $f(s)$. The transitions are: $\delta'((q, f), a) = (\delta(q, a),\; s \mapsto \delta(f(s), a))$. The initial state is $(q_0, \mathrm{id}_Q)$: the first copy starts from $q_0$, and the second has not read anything yet. The set of accepting states is $F' = \{(q, f) : f(q) \in F\}$: the second copy starts from the state $q$ reached by the first, and must arrive in $F$. By induction on $|w|$, $\hat{\delta}'((q_0, \mathrm{id}_Q), w) = (\hat{\delta}(q_0, w),\; s \mapsto \hat{\delta}(s, w))$. So $w \in L(\mathcal{A}')$ iff $\hat{\delta}(\hat{\delta}(q_0, w), w) \in F$ iff $ww \in L$.