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

A grammar $G=(\Sigma ,V,P,S)$ is a right-linear regular grammar when every production has one of the formswhere $A,B\in V$ and $w\in {\Sigma }^{\ast }$. Thus a production has at most one variable on its right-hand side, and that variable is at the right end.

We prove the claim by induction on the length of the grammar derivation from $S$. At length zero the sentential form is $S=ϵS$, which has the required form.

Suppose the current sentential form is $wA$. Because $w$ is terminal, the only symbol to which a production can apply is $A$. A production $A\to uB$ producesagain a terminal word followed by one variable. A production $A\to u$ produces the terminal word $wu$. Once a completely terminal word is reached, no further production can apply. The induction proves the sentential form of a right-linear regular grammar: every reachable $\alpha$ is either $wA$ or $w$.

In every derivation beginning at $wA$, the terminal prefix $w$ remains unchanged because no production has a terminal on its left-hand side. By the sentential-form result, each step rewrites the sole variable at the right and appends terminals immediately before its successor variable. Henceforces $v=wu$ for some $u\in {\Sigma }^{\ast }$. Removing the inert prefix $w$ from every sentential form in the derivation gives

An accepting derivation in a right-linear grammar has the formwith one active variable until the final terminal production.

If no variable repeated on any accepting derivation, an accepting derivation could contain at most $|V|$ variable occurrences. Since the production set is finite, only finitely many such derivations and hence finitely many terminal words would exist. The hypothesis that $\mathcal{L}(G)$ is infinite therefore supplies an accepting derivation in which some variable $A$ occurs twice.

Split this derivation at the two occurrences:where $u,v,z\in {\Sigma }^{\ast }$. The first segment makes $A$ an accessible variable of a regular grammar, the middle segment makes it a looping variable of a regular grammar, and the last makes it a terminable variable of a regular grammar. Thus $A$ has all three properties, proving the accessible looping terminable variable criterion.