the k-local myhill graphs provide an easy means

Question

The k-local Myhill graphs provide an easy means to generalize the suffix substitution closure property for the strictly k-local languages.

Lemma (k-Local Suffix Substitution Closure) If L is a strictly k-local language then for all strings u₁, v₁, u₂, and v₂ in Σ* and all strings x in Σ^k-1 :

u₁xv₁ ∈ L and u₂xv₂ ∈ L ⇒ u₁xv₂ ∈ L.

The justi?cation is essentially identical to that of our original suffix substitution closure lemma. If L ∈ SLk then it is recognized by an SLk automaton. In the k-local Myhill graph of that automaton, any path from ‘?' to the vertex labeled x can be put together with any path from that vertex to ‘?' to produce a path that represents a string in L.