En informática , en particular en el campo de la teoría del lenguaje formal , una familia abstracta de lenguajes es una noción matemática abstracta que generaliza características comunes a los lenguajes regulares , los lenguajes libres de contexto y los lenguajes recursivamente enumerables , y otras familias de lenguajes formales estudiados. en la literatura científica.
Definiciones formales
Un lenguaje formal es un conjunto L para el que existe un conjunto finito de símbolos abstractos Σ tal que, donde * es la operación estrella de Kleene .
Una familia de idiomas es un par ordenado, dónde
- Σ es un conjunto infinito de símbolos;
- Λ es un conjunto de lenguajes formales;
- Para cada L en Λ existe un subconjunto finito tal que ; y
- L ≠ Ø para algunos L en Λ .
Un trío es una familia de lenguas cerradas bajo -e libre de homomorfismo , inversa homomorfismo , y la intersección con el lenguaje regular.
Un trío completo, también llamado cono , es un trío cerrado bajo homomorfismo arbitrario.
Un semi-AFL (completo) es un trío (completo) cerrado en unión .
Un AFL (completo) es un semi-AFL (completo) cerrado bajo concatenación y el Kleene plus .
Algunas familias de idiomas
Los siguientes son algunos resultados simples del estudio de familias abstractas de lenguajes. [1]
Dentro de la jerarquía de Chomsky , los lenguajes regulares, los lenguajes libres de contexto y los lenguajes enumerables recursivamente son todos AFL completos. Sin embargo, los lenguajes sensibles al contexto y los lenguajes recursivos son AFL, pero no AFL completos porque no están cerrados bajo homomorfismos arbitrarios.
La familia de lenguas regulares está contenida dentro de cualquier cono (trío completo). Otras categorías de familias abstractas son identificables por cierre bajo otras operaciones como barajar, invertir o sustituir. [2]
Orígenes
Seymour Ginsburg de la Universidad del Sur de California y Sheila Greibach de la Universidad de Harvard presentaron el primer artículo de teoría de AFL en el Octavo Simposio Anual de IEEE sobre Teoría de Conmutación y Autómatas en 1967. [3]
Notas
- ^ Mateescu, A .; Salomaa, A. (2001) [1994], "Familia abstracta de lenguajes" , Enciclopedia de Matemáticas , EMS Press
- ^ Păun, Gh. (2001) [1994], "Operaciones AFL" , Enciclopedia de Matemáticas , EMS Press
- ^ Ginsburg y Greibach (1967)
Referencias
- Ginsburg, Seymour; Greibach, Sheila (1967). "Familias abstractas de lenguas". Conference Record de 1967 Octavo Simposio Anual sobre conmutación y Teoría de Autómatas, 18-20 de octubre de 1967, Austin, Texas, EE.UU. . IEEE. págs. 128-139.
- Seymour Ginsburg, Propiedades teóricas algebraicas y autómatas de los lenguajes formales , Holanda Septentrional, 1975, ISBN 0-7204-2506-9 .
- John E. Hopcroft y Jeffrey D. Ullman, Introducción a la teoría, los lenguajes y la computación de los autómatas , Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X . Capítulo 11: Propiedades de cierre de familias de lenguajes.
- Mateescu, Alexandru; Salomaa, Arto (1997). "Capítulo 4: Aspectos de la teoría del lenguaje clásico". En Rozenberg, Grzegorz; Salomaa, Arto (eds.). Manual de lenguajes formales. Volumen I: Palabra, lenguaje, gramática . Springer-Verlag. págs. 175–252. ISBN 3-540-61486-9.