Familia abstracta de lenguas
En informática teórica , y en particular teoría de lenguajes formales , el término familia de lenguajes abstractos se refiere a un concepto que generaliza las características comunes del lenguaje racional , los lenguajes algebraicos , a lenguajes recursivamente enumerables y muchas otras familias de lenguajes formales.
Definiciones
- Un lenguaje formal es un conjunto de palabras sobre un alfabeto finito , es decir, una parte del monoide libre , donde * denota la estrella de Kleene .
- Una familia de lenguas es un par formado a partir de un alfabeto infinito denotado y, para cualquier parte finita de , a partir de un conjunto de lenguas formales .
- Un cono racional (llamado trío completo en inglés) es una familia de lenguajes cerrados para las operaciones de morfismo, morfismo inverso e intersección con lenguajes racionales.
- Un cono racional fiel (llamado trío en inglés) es una familia de lenguajes cerrados para operaciones de morfismo que no se borra, morfismo inverso e intersección con lenguajes racionales.
- Una familia de lenguas está racionalmente cerrada si está cerrada por operaciones de unión, producto y estrella de Kleene .
- Una familia abstracta de lenguas ( familia abstracta completa de lenguas o AFL completo en inglés) es un cono racional que además está racionalmente cerrado.
- Una familia de lenguas abstractas fieles ( familia abstracta de lenguas o AFL en inglés) es un cono racional fiel racionalmente cerrado.
También nos encontramos con la noción de semi-AFL para un cono racional cerrado por unión.
Ejemplos de familias abstractas de lenguajes y propiedades
- Los lenguajes racionales forman una familia abstracta de lenguajes.
- Los lenguajes algebraicos forman una familia de lenguajes abstractos.
- Los lenguajes sensibles al contexto forman una familia abstracta de lenguajes fieles, porque no están cerrados por ningún morfismo.
- Los lenguajes recursivamente enumerables forman una familia abstracta de lenguajes fieles, así como los lenguajes recursivos .
- Cada cono racional contiene la familia de lenguajes racionales.
- Los lenguajes lineales forman un cono racional cerrado por unión. Asimismo, los lenguajes cuasi-racionales forman un cono racional cerrado por unión. Los lenguajes lineales no son racionalmente cerrados, los lenguajes cuasi racionales lo son.
- Otras operaciones no se expresan mediante operaciones de transducción racional o cierre por operaciones racionales. Estos son, en particular, la reproducción aleatoria , la imagen especular, las sustituciones.
Origen
Seymour Ginsburg y Sheila Greibach presentaron el primer artículo sobre familias abstractas de lenguajes en el octavo simposio de la serie Symposium on Switching and Automata Theory en 1967.
Notas
- (en) Ginsburg y Greibach (1967) .
Referencias
- (en) Seymour Ginsburg y Sheila Greibach, "Abstract Families of Languages" , en el octavo simposio anual sobre la teoría de la conmutación y los autómatas, 18-20 de octubre de 1967, Austin, Texas, EE . UU. , IEEE,1967, p. 128-139
- (en) Seymour Ginsburg , Propiedades teóricas algebraicas y autómatas de los lenguajes formales , Holanda Septentrional,1975( ISBN 0-7204-2506-9 )
- (en) 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,1979( ISBN 0-201-02988-X ) , "Capítulo 11: Propiedades de cierre de familias de idiomas"
- (en) Alexandru Mateescu y Arto Salomaa , “Capítulo 4: Aspectos de la teoría del lenguaje clásico” , en G. Rozenberg, A. Salomaa (editores), Handbook of Formal Languages , vol. 1: Palabra, idioma, gramática , Springer Verlag,1997( ISBN 978-3540604204 ) , pág. 175-252