Local language (formal language)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at a "window" of length two.[1] Equivalently, it is a language recognised by a local automaton, a class of deterministic finite automaton.[2]

Formally, we define a language L over an alphabet A 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, suffix and the set of factors of w of length k; a language is locally testable if it is k-testable for some k.[5] A local language is 2-testable.[1]

Examples[edit]

  • Over the alphabet {a,b}[4]
 aa^*,\ \{ab\} \ .

Properties[edit]

References[edit]

  1. ^ a b c d Salomaa (1981) p.97
  2. ^ Lawson (2004) p.130
  3. ^ Lawson (2004) p.129
  4. ^ a b c Sakarovitch (2009) p.228
  5. ^ McNaughton & Papert (1971) p.14
  6. ^ Lawson (2004) p.132
  7. ^ McNaughton & Papert (1971) p.18