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 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]
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]\ .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e32cc6bcb12d719a8bd7b714c95e953b40fdb17)
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
- ^ a b c d Salomaa (1981) p.97
- ^ Lawson (2004) p.130
- ^ Lawson (2004) p.129
- ^ a b c Sakarovitch (2009) p.228
- ^ Caron, Pascal (2000-07-06). "Families of locally testable languages". Theoretical Computer Science. 242 (1): 361–376. doi:10.1016/S0304-3975(98)00332-6. ISSN 0304-3975.
- ^ McNaughton & Papert (1971) p.14
- ^ Lawson (2004) p.132
- ^ McNaughton & Papert (1971) p.18
- 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.