Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 21 / 2

The minimal deterministic finite automaton is unique up to an isomorphism preserving the initial state, transitions and accepting states. We use complete deterministic finite automata over the fixed alphabet; the PDF's abbreviation FDA has this meaning. State names themselves cannot be unique.

For words $u,v\in {\Sigma }^{\ast }$, introduce the Myhill-Nerode equivalenceIt is an equivalence relation, and appending the same letter to equivalent words preserves it: a suffix $w$ after $ua$ is the suffix $aw$ after $u$. Since $L$ is a regular language, take any recognizing deterministic finite automaton. Words reaching the same state are equivalent, since every further suffix gives the same computation. Thus ${\sim }_L$ has finite index.

The canonical residual automaton has one state $[u]$ for each class, initial state $[ϵ]$, transition $[u]\stackrel{a}{\to }[ua]$, and accepting states those with $u\in L$. These choices are well-defined by Myhill-Nerode equivalence. Induction on the input length shows that reading $u$ reaches $[u]$, so the deterministic finite automaton recognizes $L$, and all its states are accessible states of a deterministic finite automaton. The same state can be described by the left quotient of a formal languageTwo states are different precisely when some suffix distinguishes their acceptance behavior.

Every recognizing deterministic finite automaton has at least as many states as there are classes: pick a representative from each class; two different representatives cannot reach the same state. The canonical residual automaton attains this bound, and therefore is a minimal deterministic finite automaton.

For uniqueness, let $\mathcal{A}$ be any minimal deterministic finite automaton. All its states are accessible, since removing inaccessible states leaves a complete recognizing deterministic finite automaton with fewer states. Map a state reached by $u$ to $[u]$. This is well-defined because two words reaching the same state are equivalent. It is surjective because every class has a representative. Both sets have the minimal number of states, so it is a bijection. It preserves the initial state and transitions by construction, and preserves accepting states by taking the empty word as the suffix. This is the required isomorphism with the canonical residual automaton, provingThe empty word is included throughout, and empty or universal regular languages have the corresponding one-state complete deterministic finite automata.

Yes: regular languages are closed under the shuffle of formal languages. The construction must allow letters common to both alphabets to be assigned to either input word.

Take complete deterministic finite automata ${\mathcal{A}}_i=(Q_i,{\Sigma }_i,{\delta }_i,s_i,F_i)$ recognizing $L_i$. Construct a nondeterministic finite automaton on $Q_1\times Q_2$ over $\Sigma ={\Sigma }_1\cup {\Sigma }_2$. Its initial state is $(s_1,s_2)$ and its accepting states form $F_1\times F_2$. On a letter $a$, its possible moves from $(p,q)$ areBoth moves are allowed when $a$ belongs to both alphabets. They may coincide; that causes no difficulty.

For every run, record whether each move updated the first or the second coordinate. The letters assigned to each coordinate, in their original order, form two words $u_1,u_2$. The final coordinate states are exactly the states reached by reading $u_i$ in ${\mathcal{A}}_i$. Thus an accepting run expresses the input as an interleaving of a word of $L_1$ and a word of $L_2$.

Conversely, given such an interleaving, assign each input position to the word from which it came. The corresponding choices of transitions form a run ending in $F_1\times F_2$. This proves equality between the recognized formal language and the shuffle of formal languages, in both directions. No assumption of disjoint alphabets is needed. If one contributing word is the empty word, no move need update that coordinate; the initial pair is accepting exactly when both empty words are accepted.

Apply the powerset construction to this nondeterministic finite automaton to obtain a deterministic finite automaton. In particular,