Familia abstracta de lenguajes

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 estudiadas. en la literatura científica.

Definiciones formales

Un lenguaje formal es un conjunto L para el cual existe un conjunto finito de símbolos abstractos Σ tal que , donde * es la operación estrella de Kleene . ${\displaystyle L\subseteq \Sigma ^{*}}$

Una familia de lenguas es un par ordenado , donde ${\displaystyle (\Sigma ,\Lambda )}$

1. Σ es un conjunto infinito de símbolos;
2. Λ es un conjunto de lenguajes formales;
3. Para cada L en Λ existe un subconjunto finito tal que ; y ${\displaystyle \Sigma _{1}\subseteq \Sigma }$ ${\displaystyle L\subseteq \Sigma _{1}^{*}}$
4. L ≠ Ø para algunos L en Λ .

Un trío es una familia de lenguas cerradas bajo homomorfismos que no introducen la 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 .

Una AFL (completa) es una semi-AFL (completa) cerrada bajo concatenación y Kleene plus .

Algunas familias de lenguas

Los siguientes son algunos resultados simples del estudio de familias abstractas de lenguas. ^[1]

Dentro de la jerarquía de Chomsky , los lenguajes regulares, los lenguajes libres de contexto y los lenguajes recursivamente enumerables 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 se pueden identificar mediante el cierre de otras operaciones como la reproducción aleatoria, la inversión o la sustitución. ^[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 teórico de la AFL en el Octavo Simposio Anual del IEEE sobre Teoría de Conmutaciones y Autómatas en 1967. ^[3]

Notas

1. Mateescu, A.; Salomaa, A. (2001) [1994], "Familia de lenguas abstractas", Enciclopedia de Matemáticas , EMS Press
2. Păun, Gh. (2001) [1994], "Operaciones AFL", Enciclopedia de Matemáticas , EMS Press
3. Ginsburg y Greibach (1967)

Referencias

• Ginsburg, Seymour; Greibach, Sheila (1967). "Familias abstractas de lenguas". Acta de la conferencia del octavo simposio anual de 1967 sobre teoría de conmutación y autómatas, 18 a 20 de octubre de 1967, Austin, Texas, EE. UU . IEEE. págs. 128-139.
• Seymour Ginsburg, Propiedades teóricas algebraicas y de 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 lenguas. 
• 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. Tomo I: Palabra, lengua, gramática . Springer-Verlag. págs. 175-252. ISBN 3-540-61486-9.