Altura de la estrella de la expresión regular y el lenguaje regular

La altura de la estrella se relaciona con el campo de la teoría de la computación (TOC). Se utiliza para indicar la complejidad estructural de las expresiones regulares y los lenguajes regulares. Aquí la complejidad se relaciona con la máxima profundidad de anidamiento de las estrellas Kleene presentes en una expresión regular.
Cabe señalar aquí que un lenguaje regular puede estar representado por expresiones regulares que no son únicas, pero equivalentes. Estas expresiones regulares pueden tener diferentes alturas de estrella dependiendo de su complejidad estructural (es decir, anidamiento). Pero la altura de la estrella de un lenguaje regular es un número único y es igual a la altura mínima de la estrella de cualquier expresión regular que represente ese idioma. En este contexto , la altura de la estrella generalizadaes una terminología apropiada, que define la profundidad mínima de anidamiento de las estrellas Kleene para describir el lenguaje por medio de una expresión regular generalizada. Por ejemplo:

El idioma “aba” sobre el conjunto de alfabetos {a, b} se puede generar usando expresiones regulares,

(a + b)* ...... (1) Star height = 1
(a* b*)* ...... (2) Star height = 2

Pero consideramos la altura mínima de la estrella. Por lo tanto, la altura de la estrella del lenguaje regular “aba” es uno.

La altura de la estrella también se define para las expresiones regulares como la profundidad máxima de anidamiento de las estrellas Kleene que aparecen en esa expresión. Para indicar formalmente la altura de la estrella, «h» de una expresión regular, uno puede escribir como,

h( ) = 0, donde está el conjunto vacío
h( ) = 0, donde está la string vacía
h(t) = 0, donde t puede ser cualquier símbolo terminal de un conjunto alfabético
h(EF) = max(h(E ), h(F)), donde E, F denota expresiones regulares
h(E*) = h(E) + 1

Algunos ejemplos son:

• h(a*(ba*)*) = 2
• h((ab*) + (a* ab*)*b)*) = 3
• h(a) = 0

El Prof. Eggan trató de dar una relación entre la complejidad del bucle de un autómata que acepta un lenguaje L y la altura de la estrella del lenguaje, L.
La altura de la estrella de un lenguaje, L es igual a la complejidad mínima del bucle de un autómata que acepta, L. También se puede afirmar que la complejidad del bucle de un autómata que es a la vez accesible (es decir, autómatas construidos eliminando todos los estados no accesibles y cualquier transición hacia o desde ellos) y coaccesible (es decir, un estado q de un se dice que un autómata es coaccesible si hay una string s que nos lleva de q a un estado marcado) es el mínimo de alturas de estrella de expresiones regulares obtenidas por diferentes ejecuciones posibles del método de eliminación de estado (o algoritmo BMC).

Es evidente que un lenguaje regular de altura de estrella cero puede representar solo un número finito de lenguajes regulares. La altura de estrella generalizada considera que tomar el complemento de una expresión regular no conduciría a un aumento en la altura de la estrella. Esta consideración arroja interesantes resultados a su disposición.

Por ejemplo, considere el conjunto de alfabetos {x, y}. La altura de la estrella de la expresión regular para el lenguaje regular «todas las strings que comienzan y terminan con x», es decir

h(x(x + y)*x+x) = 1, since only one level of Kleene nesting exists

Pero el mismo idioma también se puede representar mediante la expresión regular x ^cx + x, porque ^c denota un conjunto de todas las strings sobre los alfabetos de entrada.

Now, h(x ^c x + x) = 0, as no Kleene nesting present

Por lo tanto, la altura de estrella generalizada del idioma es 0 aunque su altura de estrella sea 1.