In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at the first and last symbol and each two-symbol substring of the word. ^[1] Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton. ^[2]

Formally, a language L over an alphabet A is defined 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. ^[3] This corresponds to the regular expression ^{[1] [4]}

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

More generally, a k-testable language L is one for which membership of a word w in L depends only on the prefix and suffix of length k and the set of factors of w of length k; ^[5] a language is locally testable if it is k-testable for some k. ^[6] A local language is 2-testable. ^[1]

Examples

• Over the alphabet {a,b,,} ^[4]

${\displaystyle aa^{*},\ [ab]\ .}$

Properties

• The family of local languages over A is closed under intersection and Kleene star, but not complement, union or concatenation. ^[4]
• Every regular language not containing the empty string is the image of a local language under a strictly alphabetic morphism. ^{[1] [7] [8]}

References

• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN  1-58488-255-7. Zbl  1086.68074.
• McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. Vol. 65. With an appendix by William Henneman. MIT Press. ISBN  0-262-13076-9. Zbl  0232.94024.
• 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.
• Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN  0-273-08522-0. Zbl  0487.68064.