Problema de la altura de la estrella

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

¿Pueden expresarse todos los idiomas regulares usando expresiones regulares de altura de estrellas limitadas?

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 usando expresiones regulares de altura de estrella limitada, es decir, con una profundidad de anidación limitada de estrellas Kleene. Específicamente, ¿siempre es suficiente una profundidad de anidamiento de uno? Si no, ¿hay un algoritmo para determinar cuántos se requieren? El problema fue planteado por Eggan (1963).

Familias de lenguajes regulares con altura de estrella ilimitada

La primera pregunta fue respondida negativamente cuando en 1963, Eggan dio ejemplos de lenguajes regulares de altura de estrella n para cada n. Aquí, la altura de la estrella h(L) de un lenguaje regular L se define como la altura mínima de la estrella entre todas las 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:

{begin{alignedat}{2}e_{1}&=a_{1}^{*}\e_{2}&=left(a_{1}^{*}a_{2}^{*}a_{3}right)^{*}\e_{3}&=left(left(a_{1}^{*}a_{2}^{*}a_{3}right)^{*}left(a_{4}^{*}a_{5}^{*}a_{6}right)^{*}a_{7}right)^{*}\e_{4}&=left(left(left(a_{1}^{*}a_{2}^{*}a_{3}right)^{*}left(a_{4}^{*}a_{5}^{*}a_{6}right)^{*}a_{7}right)^{*}left(left(a_{8}^{*}a_{9}^{*}a_{{10}}right)^{*}left(a_{{11}}^{*}a_{{12}}^{*}a_{{13}}right)^{*}a_{{14}}right)^{*}a_{{15}}right)^{*}end{alignedat}}

El principio de construcción de estas expresiones es esa expresión $e_{{n+1}}$ se obtiene concatenando dos copias de $e_{n}$ , adecuadamente renombrar las letras de la segunda copia usando símbolos alfabéticos frescos, concatenando el resultado con otro símbolo alfabético fresco, y luego rodeando la expresión resultante con una estrella kleene. La parte restante, más difícil, es demostrar que $e_{n}$ no hay una expresión regular equivalente de la altura de la estrella menos que n; una prueba se da en (Eggan 1963).

Sin embargo, los ejemplos de Eggan usan un gran alfabeto, de tamaño 2ⁿ-1 para el lenguaje con altura de estrella n. Por lo tanto, preguntó si también podemos encontrar ejemplos sobre alfabetos binarios. Esto fue demostrado ser cierto poco después por Dejaan " Schützenberger (1966). Sus ejemplos pueden ser descritos por una familia inductivamente definida de expresiones regulares sobre el alfabeto binario ${a,b}$ como sigue –cf. Salomaa (1981):

{begin{alignedat}{2}e_{1}&=(ab)^{*}\e_{2}&=left(aa(ab)^{*}bb(ab)^{*}right)^{*}\e_{3}&=left(aaaaleft(aa(ab)^{*}bb(ab)^{*}right)^{*}bbbbleft(aa(ab)^{*}bb(ab)^{*}right)^{*}right)^{*}\,&cdots \e_{{n+1}}&=(,underbrace {acdots a}_{{2^{n}}},cdot ,e_{n},cdot ,underbrace {bcdots b}_{{2^{n}}},cdot ,e_{n},)^{*}end{alignedat}}

Una vez más, se necesita una prueba rigurosa para el hecho de que $e_{n}$ no admite una expresión regular equivalente de la altura de las estrellas inferiores. Las pruebas son dadas por (Dejean " Schützenberger 1966) y por (Salomaa 1981).

Cálculo de la altura de la estrella de los idiomas regulares

Por el contrario, 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 grupos puros 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 lenguaje regular. El algoritmo no era nada práctico, siendo de complejidad no elemental. Para ilustrar el inmenso consumo de recursos de ese algoritmo, Lombardy y Sakarovitch (2002) dan algunas cifras reales:

[El procedimiento descrito por Hashiguchi] conduce a computaciones que son por lejos imposibles, incluso para ejemplos muy pequeños. Por ejemplo, si L es aceptado por un autómata de 4 estados de la complejidad del bucle 3 (y con un pequeño 10 elemento monoide de transición), entonces un muy bajo del número de idiomas que se probarán con L para la igualdad es: $left(10^{{10^{{10}}}}right)^{{left(10^{{10^{{10}}}}right)^{{left(10^{{10^{{10}}}}right)}}}}.$
—S. Lombardy y J. Sakarovitch, Star Height of Reversible Languages and Universal Automata, LATIN 2002

Note que solo el número $10^{10^{10}}$ tiene 10 mil millones de ceros cuando se escribe en notación decimal, y ya por lejos más grande que el número de átomos en el universo observable.

Kirsten ideó un algoritmo mucho más eficiente que el procedimiento de Hashiguchi en 2005. Este algoritmo se ejecuta, para un autómata finito no determinista dado como entrada, dentro de un espacio exponencial doble. Sin embargo, los requisitos de recursos de este algoritmo aún superan con creces los márgenes de lo que se considera factible en la práctica.

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 ha implementado en 2017 en la suite de herramientas Stamina.

Contenido relacionado

Más resultados...