Local language (formal language)

From HandWiki

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]

[math]\displaystyle{ (RA^* \cap A^*S) \setminus A^*FA^* \ . }[/math]

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]
[math]\displaystyle{ aa^*,\ [ab] \ . }[/math]

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

  1. 1.0 1.1 1.2 1.3 Salomaa (1981) p.97
  2. Lawson (2004) p.130
  3. Lawson (2004) p.129
  4. 4.0 4.1 4.2 Sakarovitch (2009) p.228
  5. 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. https://www.sciencedirect.com/science/article/pii/S0304397598003326. 
  6. McNaughton & Papert (1971) p.14
  7. Lawson (2004) p.132
  8. McNaughton & Papert (1971) p.18