Abstract family of languages

From HandWiki

In computer science, in particular in the field of formal language theory, an abstract family of languages is an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other families of formal languages studied in the scientific literature.

Formal definitions

A formal language is a set L for which there exists a finite set of abstract symbols Σ such that [math]\displaystyle{ L \subseteq\Sigma^* }[/math], where * is the Kleene star operation.

A family of languages is an ordered pair [math]\displaystyle{ (\Sigma,\Lambda) }[/math], where

  1. Σ is an infinite set of symbols;
  2. Λ is a set of formal languages;
  3. For each L in Λ there exists a finite subset [math]\displaystyle{ \Sigma_1 \subseteq \Sigma }[/math] such that [math]\displaystyle{ L \subseteq \Sigma_1^* }[/math]; and
  4. L ≠ Ø for some L in Λ.

A trio is a family of languages closed under homomorphisms that do not introduce the empty word, inverse homomorphisms, and intersections with a regular language.

A full trio, also called a cone, is a trio closed under arbitrary homomorphism.

A (full) semi-AFL is a (full) trio closed under union.

A (full) AFL is a (full) semi-AFL closed under concatenation and the Kleene plus.

Some families of languages

The following are some simple results from the study of abstract families of languages.[1]

Within the Chomsky hierarchy, the regular languages, the context-free languages, and the recursively enumerable languages are all full AFLs. However, the context sensitive languages and the recursive languages are AFLs, but not full AFLs because they are not closed under arbitrary homomorphisms.

The family of regular languages are contained within any cone (full trio). Other categories of abstract families are identifiable by closure under other operations such as shuffle, reversal, or substitution.[2]

Origins

Seymour Ginsburg of the University of Southern California and Sheila Greibach of Harvard University presented the first AFL theory paper at the IEEE Eighth Annual Symposium on Switching and Automata Theory in 1967.[3]

Notes

  1. ↑ Hazewinkel, Michiel, ed. (2001), "Abstract family of languages", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Abstract_family_of_languages 
  2. ↑ Hazewinkel, Michiel, ed. (2001), "AFL operations", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=AFL_operations 
  3. ↑ (Ginsburg Greibach)

References

  • Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". IEEE. pp. 128–139. 
  • Seymour Ginsburg, Algebraic and automata theoretic properties of formal languages, North-Holland, 1975, ISBN:0-7204-2506-9.
  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN:0-201-02988-X. Chapter 11: Closure properties of families of languages.
  • Mateescu, Alexandru; Salomaa, Arto (1997). "Chapter 4: Aspects of Classical Language Theory". in Rozenberg, Grzegorz; Salomaa, Arto. Handbook of Formal Languages. Volume I: Word, language, grammar. Springer-Verlag. pp. 175–252. ISBN 3-540-61486-9. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Abstract_family_of_languages&oldid=3008190"