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.
Un lenguaje formal es un conjunto L para el cual existe un conjunto finito de símbolos abstractos Σ tales que , donde * es la operación de estrella de Kleene .
Una familia de lenguas es un par ordenado , donde
Un trío es una familia de lenguas cerradas bajo homomorfismos que no introducen palabra vacía, homomorfismos inversos e intersecciones con una lengua regular.
Un trío completo, también llamado cono , es un trío cerrado bajo homomorfismo arbitrario.
Una semi-AFL (completa) es un trío (completo) cerrado bajo unión .
Un AFL (completo) es un semi-AFL (completo) cerrado bajo concatenación y Kleene plus .
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 recursivamente enumerables son todos lenguajes AFL completos. Sin embargo, los lenguajes sensibles al contexto y los lenguajes recursivos son lenguajes AFL, pero no completos porque no están cerrados bajo homomorfismos arbitrarios.
La familia de lenguajes regulares está contenida dentro de cualquier cono (trío completo). Otras categorías de familias abstractas se pueden identificar por su clausura bajo otras operaciones como la mezcla, la inversión o la sustitución. [2]
Seymour Ginsburg, de la Universidad del Sur de California , y Sheila Greibach, de la Universidad de Harvard, presentaron el primer artículo sobre la teoría de autómatas y conmutación en el Octavo Simposio Anual del IEEE sobre Teoría de Autómatas y Conmutación en 1967. [3]
