we have now dened classes of k-local languages

Question

We have now de?ned classes of k-local languages for all k ≥ 2. Together, these classes form the Strictly Local Languages in general.

De?nition (Strictly Local Languages) A language L is strictly local (L ∈ SL) iff it is strictly k-local for some k.

 

Again, we can generalize the work we have done so far to establish properties of the class of strictly local languages as a whole.

Theorem 3 ((General) Suffix Substitution Closure) A language L is strictly local iff there is some k such that, 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.