Local language (formal language)

In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at a "window" of length two. Equivalently, it is a language recognised by a local automaton, a class of deterministic finite automaton.

Formally, we define a language L over an alphabet A to be local if there are subsets R and S of A and a subset F of A×A such that a word w is in L if and only if the first letter of w is in R, the last letter of w is in S and no factor of length 2 in w is in F. This corresponds to the regular expression

$(RA^{*}\cap A^{*}S)\setminus A^{*}FA^{*}\ .$

Examples

• Over the alphabet {a,b}

$aa^{*},\ \{ab\}\ .$

Properties

• The family of local languages over A is closed under intersection and Kleene star.
• Every regular language not containing the empty string is the image of a local language under a strictly alphabetic morphism.

References

• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. Zbl 1086.68074.
• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.