En informática teórica , más precisamente en la teoría de lenguajes formales , la altura de estrella es una medida de la complejidad estructural de las expresiones regulares y los lenguajes regulares . La altura de estrella de una expresión regular es igual a la profundidad máxima de anidación de estrellas que aparecen en esa expresión. La altura de estrella de un lenguaje regular es la altura de estrella más baja de cualquier expresión regular para ese lenguaje. El concepto de altura de estrella fue definido y estudiado por primera vez por Eggan (1963).
De manera más formal, la altura de estrella de una expresión regular E sobre un alfabeto finito A se define inductivamente de la siguiente manera:
Aquí, está la expresión regular especial que denota el conjunto vacío y ε la expresión regular especial que denota la palabra vacía ; E y F son expresiones regulares arbitrarias.
La altura de estrella h ( L ) de un lenguaje regular L se define como la altura de estrella mínima entre todas las expresiones regulares que representan a L . La intuición aquí es que si el lenguaje L tiene una altura de estrella grande, entonces es en cierto sentido inherentemente complejo, ya que no puede describirse por medio de una expresión regular "fácil", de baja altura de estrella.
Si bien calcular la altura de estrella de una expresión regular es fácil, determinar la altura de estrella de un lenguaje puede ser a veces complicado. Por ejemplo, la expresión regular
sobre el alfabeto A = {a,b} tiene una altura de estrella de 2. Sin embargo, el lenguaje descrito es solo el conjunto de todas las palabras que terminan en a : por lo tanto, el lenguaje también puede describirse mediante la expresión
que tiene una altura de estrella de solo 1. Para demostrar que este idioma tiene una altura de estrella de 1, todavía hay que descartar que pueda describirse mediante una expresión regular de una altura de estrella menor. Para nuestro ejemplo, esto se puede hacer mediante una prueba indirecta: se demuestra que un idioma con una altura de estrella de 0 contiene solo un número finito de palabras. Dado que el idioma en cuestión es infinito, no puede tener una altura de estrella de 0.
La altura de estrella de un idioma de grupo es computable: por ejemplo, la altura de estrella del idioma sobre { a , b } en el que el número de ocurrencias de a y b son congruentes módulo 2 n es n . [1]
En su estudio seminal sobre la altura de estrella de los lenguajes regulares, Eggan (1963) estableció una relación entre las teorías de expresiones regulares, autómatas finitos y grafos dirigidos . En años posteriores, esta relación se conoció como el teorema de Eggan , cf. Sakarovitch (2009). Recordemos algunos conceptos de la teoría de grafos y la teoría de autómatas .
En teoría de grafos, el rango de ciclo r ( G ) de un grafo dirigido (dígrafo) G = ( V , E ) se define inductivamente de la siguiente manera:
En la teoría de autómatas, un autómata finito no determinista con ε-transiciones (ε-NFA) se define como una 5-tupla , ( Q , Σ, δ , q 0 , F ), que consta de
Una palabra w ∈ Σ * es aceptada por el ε-NFA si existe un camino dirigido desde el estado inicial q 0 hasta algún estado final en F usando aristas de δ , de modo que la concatenación de todas las etiquetas visitadas a lo largo del camino produce la palabra w . El conjunto de todas las palabras sobre Σ * aceptadas por el autómata es el lenguaje aceptado por el autómata A .
Cuando hablamos de propiedades digráficas de un autómata finito no determinista A con conjunto de estados Q , naturalmente nos referimos al dígrafo con conjunto de vértices Q inducido por su relación de transición. Ahora el teorema se enuncia de la siguiente manera.
Las pruebas de este teorema las dan Eggan (1963) y, más recientemente, Sakarovitch (2009).
La definición anterior supone que las expresiones regulares se construyen a partir de los elementos del alfabeto A utilizando únicamente los operadores estándar unión de conjuntos , concatenación y estrella de Kleene . Las expresiones regulares generalizadas se definen igual que las expresiones regulares, pero aquí también se permite el operador de complemento de conjunto (el complemento siempre se toma con respecto al conjunto de todas las palabras sobre A). Si modificamos la definición de modo que tomar complementos no aumente la altura de la estrella, es decir,
Podemos definir la altura de estrella generalizada de un lenguaje regular L como la altura de estrella mínima entre todas las expresiones regulares generalizadas que representan a L. Es un problema abierto si algunos lenguajes solo pueden expresarse con una altura de estrella generalizada mayor que uno: este es el problema de la altura de estrella generalizada .
Nótese que, mientras que es inmediato que un lenguaje con una altura de estrella (ordinaria) de 0 puede contener solo un número finito de palabras, existen infinitos lenguajes que tienen una altura de estrella generalizada de 0. Por ejemplo, la expresión regular
que vimos en el ejemplo anterior, se puede describir de manera equivalente mediante la expresión regular generalizada
ya que el complemento del conjunto vacío es precisamente el conjunto de todas las palabras sobre A. Así, el conjunto de todas las palabras sobre el alfabeto A que terminan en la letra a tiene altura de estrella uno, mientras que su altura de estrella generalizada es igual a cero.
Los idiomas de altura de estrella generalizada cero también se denominan idiomas sin estrellas . Se puede demostrar que un idioma L es sin estrellas si y solo si su monoide sintáctico es aperiódico (Schützenberger (1965)).
