Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 12I (Automata & Formal Languages)

Extend $\delta :Q\times \Sigma \to Q$ tobyThe extended transition function of a deterministic finite automaton processes a whole word from left to right. The language accepted by $D$ is

Let $N=|Q|$. The pumping lemma for regular languages states that every $w\in L(D)$ with $|w|\ge N$ can be writtenwithThus one may take the pumping number to be exactly the number $N$ of states of the given automaton, whether or not all of them are accessible.

For $0\le j\le 9$, consider the ten prefixesIf $0\le i<j\le 9$, appendThenbecause $i+11-j\le 10$, whereasIndeed, in a word ending in one $a$, the prefix before the final positive run of $a$'s must have length at most ten. Hence every pair $u_i,u_j$ is distinguished by some suffix. They occupy ten distinct Myhill-Nerode equivalence classes, so the minimal deterministic finite automaton for $L$ has at least ten states.

Suppose first that $A$ is a regular language, accepted by a deterministic finite automaton $D$. If two words reach the same state, then every continuation is accepted from both or rejected from both. Thus they are equivalent under ${\sim }_A$, and the number of equivalence classes is at most the finite number of states of $D$.

Conversely, suppose ${\sim }_A$ has finitely many classes. Define a deterministic automaton byandThe transition is well defined: if $v{\sim }_{A}w$, then for every suffix $u$,so $va{\sim }_{A}wa$. Likewise, membership in $F$ is independent of the representative by taking the empty suffix in the definition of ${\sim }_A$. Induction givesso the automaton accepts exactly $A$. It has finitely many states, and therefore $A$ is regular. This proves the Myhill-Nerode theorem in the stated formulation. The assumption $\epsilon \notin A$ merely says that the initial state is not accepting.