Local language (formal language) explained

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]}

(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 ^[4]

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

• Book: Lawson, Mark V. . Finite automata . Chapman and Hall/CRC . 2004 . 1-58488-255-7 . 1086.68074 .
• Book: McNaughton . Robert . Papert . Seymour . Seymour Papert . With an appendix by William Henneman . Research Monograph . 65 . 1971 . Counter-free Automata . MIT Press . 0-262-13076-9 . 0232.94024 . registration .
• Book: Sakarovitch, Jacques . Elements of automata theory . Translated from the French by Reuben Thomas . Cambridge . . 2009 . 978-0-521-84425-3 . 1188.68177 .
• Book: Salomaa, Arto . Arto Salomaa

. Arto Salomaa . Jewels of Formal Language Theory . Pitman Publishing . 0-273-08522-0 . 1981 . 0487.68064 .

Notes and References

1. Salomaa (1981) p.97
2. Lawson (2004) p.130
3. Lawson (2004) p.129
4. Sakarovitch (2009) p.228
5. Caron . Pascal . 2000-07-06 . Families of locally testable languages . Theoretical Computer Science . 242 . 1 . 361–376 . 10.1016/S0304-3975(98)00332-6 . 0304-3975.
6. McNaughton & Papert (1971) p.14
7. Lawson (2004) p.132
8. McNaughton & Papert (1971) p.18