El problema de la altura de las estrellas en la teoría del lenguaje formal es la cuestión de si todos los lenguajes regulares pueden expresarse utilizando expresiones regulares de altura de estrella limitada , es decir, con una profundidad de anidación limitada de estrellas de Kleene . Específicamente, ¿es siempre suficiente una profundidad de anidación de uno? Si no es así, ¿existe un algoritmo para determinar cuántos se requieren? Eggan (1963) planteó el problema .
Familias de lenguajes regulares con altura de estrella ilimitada
La primera pregunta recibió una respuesta negativa cuando, en 1963, Eggan dio ejemplos de lenguajes regulares de altura de estrella n para cada n . En este caso, la altura estrella h ( L ) de un lenguaje regular L se define como la altura mínima de entre todas las estrellas expresiones regulares que representan L . Los primeros idiomas encontrados por Eggan (1963) se describen a continuación, dando una expresión regular para cada idioma:
El principio de construcción de estas expresiones es que la expresión se obtiene concatenando dos copias de , cambiando apropiadamente el nombre de las letras de la segunda copia usando símbolos del alfabeto nuevos, concatenando el resultado con otro símbolo del alfabeto nuevo y luego rodeando la expresión resultante con una estrella de Kleene. La parte restante, más difícil, es demostrar que parano existe una expresión regular equivalente de altura de estrella menor que n ; se da una prueba en ( Eggan 1963 ).
Sin embargo, los ejemplos de Eggan usan un alfabeto grande , de tamaño 2 n -1 para el idioma con altura de estrella n . Por tanto, preguntó si también podemos encontrar ejemplos sobre alfabetos binarios. Esto fue demostrado poco después por Dejean y Schützenberger (1966) . Sus ejemplos pueden describirse mediante una familia de expresiones regulares definidas inductivamente sobre el alfabeto binario.como sigue – cf. Salomaa (1981) :
Nuevamente, se necesita una prueba rigurosa del hecho de que no admite una expresión regular equivalente de altura de estrella inferior. Las pruebas las dan ( Dejean y Schützenberger 1966 ) y ( Salomaa 1981 ).
Calcular la altura de las estrellas de los lenguajes regulares
En contraste, la segunda pregunta resultó ser mucho más difícil y se convirtió en un famoso problema abierto en la teoría del lenguaje formal durante más de dos décadas ( Brzozowski 1980 ). Durante años, hubo pocos avances. Los lenguajes de grupo puro fueron la primera familia interesante de lenguajes regulares para los que se demostró que el problema de la altura de las estrellas era decidible ( McNaughton 1967 ). Pero el problema general permaneció abierto durante más de 25 años hasta que fue resuelto por Hashiguchi , quien en 1988 publicó un algoritmo para determinar la altura de las estrellas de cualquier idioma regular. El algoritmo no era en absoluto práctico, ya que su complejidad no era elemental . Para ilustrar los inmensos consumos de recursos de ese algoritmo, Lombardy y Sakarovitch (2002) dan algunos números reales:
[El procedimiento descrito por Hashiguchi] conduce a cálculos que son por mucho imposibles, incluso para ejemplos muy pequeños. Por ejemplo, si L es aceptado por un autómata de 4 estados de complejidad de bucle 3 (y con un pequeño monoide de transición de 10 elementos), entonces un minorant muy bajo del número de lenguajes que se probarán con L para la igualdad es:
- S. Lombardy y J. Sakarovitch, Star Height of Reversible Languages and Universal Automata, LATIN 2002
Note que solo el numero tiene 10 mil millones de ceros cuando se escribe en notación decimal , y ya es mucho mayor que el número de átomos en el universo observable .
Un algoritmo mucho más eficiente que el procedimiento de Hashiguchi fue ideado por Kirsten en 2005. Este algoritmo se ejecuta, para un autómata finito no determinista dado como entrada, dentro de un espacio doble exponencial . Sin embargo, los requisitos de recursos de este algoritmo aún superan en gran medida los márgenes de lo que se considera prácticamente factible.
Este algoritmo ha sido optimizado y generalizado a árboles por Colcombet y Löding en 2008 ( Colcombet & Löding 2008 ), como parte de la teoría de las funciones de costos regulares. Se implementó en 2017 en la suite de herramientas Stamina. [1]
Ver también
- Problema generalizado de la altura de las estrellas
- Algoritmo de Kleene : calcula una expresión regular (generalmente de altura de estrella no mínima) para un lenguaje dado por un autómata finito determinista
Referencias
- ^ Nathanaël Fijalkow, Hugo Gimbert, Edon Kelmendi, Denis Kuperberg: " Resistencia: monoides de estabilización en la teoría de los autómatas ". CIAA 2017: 101-112 Herramienta disponible en https://github.com/nathanael-fijalkow/stamina/
Trabajos citados
- Brzozowski, Janusz A. (1980). "Problemas abiertos sobre lenguajes regulares" . En Libro, Ronald V. (ed.). Teoría del lenguaje formal: perspectivas y problemas abiertos . Nueva York: Academic Press. págs. 23–47 . ISBN 978-0-12-115350-2. (versión del informe técnico)
- Colcombet, Thomas; Löding, Christof (2008). "La profundidad de anidamiento de μ-cálculo disyuntivo para lenguajes de árbol y el problema de la limitación". CSL . Apuntes de conferencias en informática. 5213 : 416–430. doi : 10.1007 / 978-3-540-87531-4_30 . ISBN 978-3-540-87530-7. ISSN 0302-9743 .
- Dejean, Françoise; Schützenberger, Marcel-Paul (1966). "Sobre una cuestión de Eggan" . Información y control . 9 (1): 23-25. doi : 10.1016 / S0019-9958 (66) 90083-0 .
- Eggan, Lawrence C. (1963). "Gráficos de transición y la altura de las estrellas de eventos regulares" . Revista matemática de Michigan . 10 (4): 385–397. doi : 10.1307 / mmj / 1028998975 . Zbl 0173.01504 .
- McNaughton, Robert (1967). "La complejidad de bucle de eventos de grupo puro" . Información y control . 11 (1–2): 167–176. doi : 10.1016 / S0019-9958 (67) 90481-0 .
- Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Melbourne: Publicación Pitman. ISBN 978-0-273-08522-5. Zbl 0487.68063 .
Otras lecturas
- Hashiguchi, Kosaburo (1982). "Idiomas regulares de estrella de altura uno" . Información y control . 53 (2): 199–210. doi : 10.1016 / S0019-9958 (82) 91028-2 .
- Hashiguchi, Kosaburo (1988). "Algoritmos para determinar la altura relativa de la estrella y la altura de la estrella". Información y Computación . 78 (2): 124-169. doi : 10.1016 / 0890-5401 (88) 90033-8 .
- Lombardía, Sylvain; Sakarovitch, Jacques (2002). "Altura de estrella de lenguajes reversibles y autómatas universales" (PDF) . V Simposio Latinoamericano de Informática Teórica (LATIN) 2002, Vol. 2286 de LNCS . Saltador.
- Kirsten, Daniel (2005). "Autómatas del desierto de distancia y el problema de la altura de las estrellas". RAIRO - Informatique Théorique et Applications . 39 (3): 455–509. doi : 10.1051 / ita: 2005027 .
- Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . ISBN 978-0-521-84425-3. Zbl 1188.68177 .