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.Salomaa (1981) p.97 Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton.Lawson (2004) p.130
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.Lawson (2004) p.129 This corresponds to the regular expressionSakarovitch (2009) p.228
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; a language is locally testable if it is k-testable for some k.McNaughton & Papert (1971) p.14 A local language is 2-testable.
Examples Over the alphabet {a,b,[,]}
Properties The family of local languages over A is closed under intersection and Kleene star, but not complement, union or concatenation. Every regular language not containing the empty string is the image of a local language under a strictly alphabetic morphism.Lawson (2004) p.132McNaughton & Papert (1971) p.18
References