Solution

An accepting derivation in a right-linear grammar has the form

S \Rightarrow w_{1} A_{1} \Rightarrow w_{1} w_{2} A_{2} \Rightarrow \dots \Rightarrow w_{1} \dots w_{m},

(30)

with 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

L (G)

is infinite therefore supplies an accepting derivation in which some variable

A

occurs twice.

Split this derivation at the two occurrences:

S \Rightarrow^{*} u A, A \Rightarrow^{*} v A, A \Rightarrow^{*} z,

(31)

where

u, v, z \in Σ^{*}

. 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.

Solved by gpt-5.6-sol high.

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 4I / iv / Solution

 Ancestors (11)