En la informática teórica , más precisamente en la teoría de los lenguajes formales , la altura de la estrella es una medida de la complejidad estructural de las expresiones regulares y los lenguajes regulares . La altura de la estrella de una expresión regular es igual a la profundidad máxima de anidación de las estrellas que aparecen en esa expresión. La altura de estrella de un lenguaje regular es la altura mínima de estrella de cualquier expresión regular para ese lenguaje. El concepto de altura de estrella fue definido y estudiado por primera vez por Eggan (1963).
Más formalmente, la altura de la 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 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 mínima de estrella entre todas las expresiones regulares que representan L . La intuición aquí es que si el lenguaje L tiene una altura de estrella grande, entonces, en cierto sentido, es intrínsecamente complejo, ya que no puede describirse mediante una expresión regular "fácil" de altura de estrella baja.
Si bien calcular la altura de la estrella de una expresión regular es fácil, determinar la altura de la estrella de un idioma a veces puede resultar complicado. A modo de ilustración, la expresión regular
sobre el alfabeto A = {a,b} tiene estrella de altura 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 se puede describir mediante la expresión
que es solo de altura de estrella 1. Para demostrar que este lenguaje efectivamente tiene altura de estrella 1, aún es necesario descartar que pueda describirse mediante una expresión regular de altura de estrella más baja. Para nuestro ejemplo, esto se puede hacer mediante una prueba indirecta: se demuestra que un idioma de altura de estrella 0 contiene sólo un número finito de palabras. Dado que el lenguaje considerado es infinito, no puede tener una altura de estrella de 0.
La altura de la estrella de un idioma grupal es computable: por ejemplo, la altura de la estrella del idioma sobre { a , b } en el que el número de apariciones de a y b son congruentes módulo 2 n es n . [1]
En su estudio fundamental sobre la altura de las estrellas de los lenguajes regulares, Eggan (1963) estableció una relación entre las teorías de las expresiones regulares, los autómatas finitos y los grafos dirigidos . En los años siguientes, esta relación pasó a ser conocida como teorema de Eggan , cf. Sakarovich (2009). Recordamos algunos conceptos de la teoría de grafos y la teoría de autómatas .
En teoría de grafos, el rango del ciclo r ( G ) de un gráfico 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
La ε-NFA acepta una palabra w ∈ Σ * 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 produzca 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 las propiedades del dígrafo de un autómata finito no determinista A con conjunto de estados Q , naturalmente abordamos el dígrafo con conjunto de vértices Q inducido por su relación de transición. Ahora el teorema se expresa de la siguiente manera.
Eggan (1963) y, más recientemente, Sakarovitch (2009) ofrecen pruebas de este teorema.
La definición anterior supone que las expresiones regulares se construyen a partir de los elementos del alfabeto A utilizando sólo los operadores estándar conjunto unión , concatenación y estrella de Kleene . Las expresiones regulares generalizadas se definen como 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 mínima de estrella entre todas las expresiones regulares generalizadas que representan L. Es un problema abierto si algunos lenguajes sólo pueden expresarse con una altura de estrella generalizada mayor que uno: este es el problema de la altura de estrella generalizada .
Tenga en cuenta que, si bien es evidente que un lenguaje de altura de estrella (ordinaria) 0 puede contener sólo un número finito de palabras, existen infinitos lenguajes que tienen una altura de estrella generalizada 0. Por ejemplo, la expresión regular
que vimos en el ejemplo anterior, puede describirse 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 del alfabeto A que terminan en la letra a tiene una altura de estrella uno, mientras que su altura de estrella generalizada es igual a cero.
Los lenguajes de altura estelar generalizada cero también se denominan lenguajes libres de estrellas . Se puede demostrar que una lengua L está libre de estrellas si y sólo si su monoide sintáctico es aperiódico (Schützenberger (1965)).
