Altura de la estrella
En 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 anidamiento de las estrellas que aparecen en esa expresión. La altura de estrella de un idioma regular es la altura de estrella mínima de cualquier expresión regular para ese idioma. El concepto de altura de la 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í, es la expresión regular especial que denota el conjunto vacío y ε la 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 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 mediante una expresión regular "fácil", de altura de estrella baja.
Mientras que 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 ser complicado. Por ejemplo, la expresión regular
sobre el alfabeto A = {a,b} tiene altura de estrella 2. Sin embargo, el idioma descrito es solo el conjunto de todas las palabras que terminan en a : por lo tanto, el idioma también puede describirse mediante la expresión
