En informática teórica , más precisamente en la teoría de lenguajes formales , la altura de la estrella es una medida de la complejidad estructural de expresiones regulares y 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 idioma regular es la altura mínima de estrella de cualquier expresión regular para ese idioma. El concepto de altura de las estrellas fue definido y estudiado por primera vez por Eggan (1963).
Definicion formal
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:
- , , y para todos los símbolos del alfabeto una en una .
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 estrella h ( L ) de un lenguaje regular L se define como la altura mínima de entre todas las estrellas expresiones regulares que representan L . La intuición aquí es que si el lenguaje L tiene una gran altura de estrella, entonces en cierto sentido es intrínsecamente complejo, ya que no puede describirse mediante una expresión regular "fácil", de baja altura de estrella.
Ejemplos de
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 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 se puede describir mediante la expresión
que es sólo de altura de estrella 1. Para demostrar que este lenguaje tiene realmente una altura de estrella 1, todavía es necesario descartar que podría describirse mediante una expresión regular de altura de estrella más baja. Para nuestro ejemplo, esto se puede hacer mediante una demostración indirecta: se demuestra que un lenguaje de altura de estrella 0 contiene sólo un número finito de palabras. Dado que el lenguaje en consideración es infinito, no puede tener una altura de estrella 0.
La altura estrella de un idioma del grupo es computable: por ejemplo, la altura de la estrella de la lengua sobre { a , b } en el que el número de ocurrencias de un y b son congruentes módulo 2 n es n . [1]
Teorema de eggan
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/2/2c/Deterministicfiniteautomaton.svg/220px-Deterministicfiniteautomaton.svg.png)
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 gráficos dirigidos . En los años siguientes, esta relación se conoció como el teorema de Eggan , cf. Sakarovitch (2009) . Recordamos algunos conceptos de la teoría de grafos y la teoría de autómatas .
En la 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:
- Si G es acíclico , entonces r ( G ) = 0 . Esto se aplica en particular si G está vacío.
- Si G está fuertemente conectado y E no está vacío, entonces
- dónde es el dígrafo resultante de la eliminación del vértice v y todos los bordes que comienzan o terminan en v .
- Si G no está conectado firmemente, a continuación, r ( G ) es igual al rango de ciclo máximo entre todos los componentes fuertemente conectados de G .
En la teoría de autómatas, un autómata finito no determinista con transiciones ε (ε-NFA) se define como una tupla 5 , ( Q , Σ, δ , q 0 , F ), que consta de
- un conjunto finito de estados Q
- un conjunto finito de símbolos de entrada Σ
- un conjunto de marcado bordes delta , denominado relación de transición : Q × (Σ ∪ {ε}) x Q . Aquí ε denota la palabra vacía .
- un estado inicial q 0 ∈ Q
- un conjunto de estados F distinguido como estados de aceptación F ⊆ Q .
Una palabra w ∈ Σ * es aceptada por el ε-NFA si existe una ruta dirigida desde el estado inicial q 0 a algún estado final en F usando aristas de δ , de modo que la concatenación de todas las etiquetas visitadas a lo largo de la ruta produce la palabra w . El conjunto de todas las palabras más de Σ * 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 el conjunto de estados Q , naturalmente nos dirigimos al dígrafo con el conjunto de vértices Q inducido por su relación de transición. Ahora, el teorema se establece de la siguiente manera.
- Eggan del Teorema : La altura estrella de un lenguaje regular L es igual al mínimo rango ciclo entre todos los autómatas finitos no determinista con transiciones varepsilon aceptar L .
Eggan (1963) y más recientemente Sakarovitch (2009) dan pruebas de este teorema .
Altura de estrella generalizada
La definición anterior asume que las expresiones regulares se construyen a partir de los elementos del alfabeto A utilizando solo los operadores estándar, unión de conjuntos , 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 alteramos la definición de tal manera que la toma de complementos no aumente la altura de la estrella, es decir,
podemos definir la altura de la estrella generalizada de un lenguaje regular L como la altura mínima de entre todas las estrellas generalizadas expresiones regulares que representan L .
Tenga en cuenta que, mientras que es inmediato que un lenguaje de altura de estrella (ordinaria) 0 puede contener solo 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, 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 más de una . 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 de estrella cero generalizada también se denominan lenguajes sin estrellas . Se puede demostrar que una lengua L está libre de estrellas si y solo si su monoide sintáctico es aperiódico ( Schützenberger (1965) ).
Ver también
Referencias
- ↑ Sakarovitch (2009) p. 342
- Berstel, Jean; Reutenauer, Christophe (2011), Serie racional no conmutativa con aplicaciones , Enciclopedia de las matemáticas y sus aplicaciones, 137 , Cambridge: Cambridge University Press , ISBN 978-0-521-19022-0, Zbl 1250.68007
- Cohen, Rina S. (1971), "Técnicas para establecer la altura de las estrellas de conjuntos regulares", Teoría de los sistemas informáticos , 5 (2): 97-114, doi : 10.1007 / BF01702866 , ISSN 1432-4350 , Zbl 0218.94028
- Cohen, Rina S .; Brzozowski, JA (1970), "Propiedades generales de la altura de las estrellas de eventos regulares", Journal of Computer and System Sciences , 4 (3): 260-280, doi : 10.1016 / S0022-0000 (70) 80024-1 , ISSN 0022 -0000 , Zbl 0245.94038
- Eggan, Lawrence C. (1963), "Gráficos de transición y la altura de las estrellas de eventos regulares", Michigan Mathematical Journal , 10 (4): 385–397, doi : 10.1307 / mmj / 1028998975 , Zbl 0173.01504
- Sakarovitch, Jacques (2009), Elementos de la teoría de los autómatas , traducido del francés por Reuben Thomas, Cambridge: Cambridge University Press , ISBN 978-0-521-84425-3, Zbl 1188.68177
- Salomaa, Arto (1981), Joyas de la teoría del lenguaje formal , Rockville, Maryland: Computer Science Press, ISBN 978-0-914894-69-8, Zbl 0487.68064
- Schützenberger, MP (1965), "Sobre monoides finitos que tienen solo subgrupos triviales", Información y control , 8 (2): 190-194, doi : 10.1016 / S0019-9958 (65) 90108-7 , ISSN 0019-9958 , Zbl 0131.02001