Local language (formal language)
Today, Local language (formal language) is a topic that has generated great interest and debate in different areas. From politics to science, culture and society, Local language (formal language) has captured the attention of millions of people around the world. As time progresses, the importance of understanding and analyzing Local language (formal language) in depth becomes increasingly evident, as its impact extends to multiple aspects of our daily lives. In this article, we will explore the different dimensions of Local language (formal language) and its relevance in the current context, with the aim of shedding light on a topic that continues to be the object of study and reflection.
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. Equivalently, it is a language recognised by a local automaton, a particular kind of deterministic finite automaton.
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. This corresponds to the regular expression
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; a language is locally testable if it is k-testable for some k. A local language is 2-testable.
Abubakar
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.
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.