Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 12G (Automata and Formal Languages)

The pumping lemma for regular languages states that for every regular language $L$ there is an integer $N$ such that every $w\in L$ with $|w|\ge N$ can be writtenwith

To prove it, let a deterministic finite automaton with $N$ states recognize $L$. During the reading of the first $N$ symbols of an accepted word $w$, the automaton visits $N+1$ states, including the initial state. By the pigeonhole principle, two of them agree, say $q_i=q_j$ with $0\le i<j\le N$. Let $x$ be the first $i$ symbols, $y$ the next $j-i$ symbols, and $z$ the remaining suffix. Reading $y$ is a nonempty closed path from $q_i$ to itself. Traversing this path any number $r\ge 0$ of times and then reading $z$ therefore reaches the same accept state. This proves all three assertions.

Because $D$ is minimal, every state is accessible. Choose a word $u$ taking the initial state to $p$, and let the nonempty word $v$ label the closed path $\gamma$. If a word $w$ took $p$ to an accept state, thenThese words have strictly increasing lengths because $v\ne ϵ$, contradicting the assumption that $\mathcal{L}(D)$ is finite. Hence no accept state is reachable from $p$.

Suppose a path took $p$ to a state $q$. Part (i) implies that no accept state is reachable from either $p$ or $q$. Thus every possible continuation is rejected from both states, so $p$ and $q$ are indistinguishable states of a deterministic finite automaton. Distinct indistinguishable states cannot occur in a minimal deterministic finite automaton. Therefore $q=p$, and there is no path from $p$ to any other state.

Equivalently, a cycle state in a minimal deterministic finite automaton for a finite language is the unique rejecting sink.