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]

(RA*∩A*S)∖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 {a,b,[,]}[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

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

* Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7.
* McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. https://archive.org/details/CounterFre_00_McNa.
* Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. ISBN 978-0-521-84425-3.
* Salomaa, Arto (1981). Jewels of Formal Language Theory. Pitman Publishing. ISBN 0-273-08522-0.

* v
* t
* e

Automata theory: formal languages and formal grammars

| Chomsky hierarchy| Grammars| Languages| Abstract machines

|
|
|

* Type-0
* —
* Type-1
* —
* —
* —
* —
* —
* Type-2
* —
* —
* Type-3
* —
* —

* Unrestricted
* (no common name)
* Context-sensitive
* Positive range concatenation
* Indexed
* —
* Linear context-free rewriting systems
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* —
* Non-recursive

* Recursively enumerable
* Decidable
* Context-sensitive
* Positive range concatenation*
* Indexed*
* —
* Linear context-free rewriting language
* Tree-adjoining
* Context-free
* Deterministic context-free
* Visibly pushdown
* Regular
* Star-free
* Finite

* Turing machine
* Decider
* Linear-bounded
* PTIME Turing Machine
* Nested stack
* Thread automaton
* restricted Tree stack automaton
* Embedded pushdown
* Nondeterministic pushdown
* Deterministic pushdown
* Visibly pushdown
* Finite
* Counter-free (with aperiodic finite monoid)
* Acyclic finite

Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Local language (formal language). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Local_language_(formal_language)&oldid=216341"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template