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.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;{{Cite journal |last=Caron |first=Pascal |date=2000-07-06 |title=Families of locally testable languages |url=https://www.sciencedirect.com/science/article/pii/S0304397598003326 |journal=Theoretical Computer Science |volume=242 |issue=1 |pages=361–376 |doi=10.1016/S0304-3975(98)00332-6 |issn=0304-3975}} 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
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
{{reflist}}
- {{cite book | last=Lawson | first=Mark V. | title=Finite automata | publisher=Chapman and Hall/CRC | year=2004 | isbn=1-58488-255-7 | zbl=1086.68074 }}
- {{cite book | last1=McNaughton | first1=Robert | last2=Papert | first2=Seymour | author2-link=Seymour Papert | others=With an appendix by William Henneman | series=Research Monograph | volume=65 | year=1971 | title=Counter-free Automata | publisher=MIT Press | isbn=0-262-13076-9 | zbl=0232.94024 | url-access=registration | url=https://archive.org/details/CounterFre_00_McNa }}
- {{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 }}
- {{cite book | first=Arto | last=Salomaa | authorlink=Arto Salomaa | title=Jewels of Formal Language Theory | publisher=Pitman Publishing | isbn=0-273-08522-0 | year=1981 | zbl=0487.68064 }}
{{Formal languages and grammars|state=collapsed}}