Altura de la iteración del lenguaje

En informática teórica , más precisamente, en la teoría de los lenguajes formales , la altura de iteración  es una medida de la complejidad estructural de las expresiones regulares  : la altura de iteración de una expresión regular es igual a la profundidad máxima de anidamiento de asteriscos presentes en el regular. expresión. El concepto de altura de iteración fue introducido y estudiado por primera vez por Eggan (1963).

Formal definición

Formalmente, la altura de iteración de una expresión regular E sobre un alfabeto finito A se define inductivamente de la siguiente manera:

Aquí representa el conjunto vacío, ε representa la cadena vacía y E y F  son expresiones regulares arbitrarias.

La altura de iteración h ( L ) de un lenguaje regular L se define como la altura de iteración mínima de todas las expresiones regulares que representan L . Intuitivamente, si un lenguaje L tiene una altura de iteración alta, es en sí mismo complejo porque no puede describirse en términos de expresiones regulares "simples" con una altura de iteración baja.

Ejemplos

Si bien calcular la altura de iteración de una expresión regular es sencillo, la definición de la altura de iteración del lenguaje a veces puede resultar confusa. Como ejemplo, la expresión regular

sobre el alfabeto A = {a, b} tiene una altura de iteración de 2. Sin embargo, el lenguaje que se describe es el conjunto de todas las palabras que terminan en a . El mismo lenguaje se puede describir usando la expresión

,

cuya altura de iteración es solo 1. Para demostrar que la altura de iteración de un idioma es 1, debemos excluir la posibilidad de describir el idioma mediante una expresión regular con una altura de iteración más baja. Por ejemplo, esto se puede hacer indirectamente demostrando que un idioma con altura de iteración 0 contiene solo un número finito de palabras. Dado que nuestro lenguaje es infinito, no puede tener una altura de iteración de 0.

La altura de iteración del idioma del grupo es computable. Por ejemplo, la altura de una iteración de lenguaje sobre { a , b } en la que el número de apariciones de a y b son congruentes módulo 2 n es n [1] .

Teorema de Eggan

En sus estudios seminales sobre la altura de iteración de los lenguajes regulares, Eggan [2] estableció una conexión entre la teoría de expresiones regulares, la teoría de autómatas finitos y grafos dirigidos . Posteriormente, esta conexión se conoció como el teorema de Eggan [3] . Recordamos algunos conceptos de la teoría de grafos y la teoría de autómatas .

En teoría de grafos, el rango cíclico r ( G ) de un grafo dirigido (dígrafo) G  = ( V ,  E ) se define inductivamente como sigue:

 donde G - v es el dígrafo obtenido al eliminar el vértice v y todos los arcos que comienzan o terminan en v.

En la teoría de los autómatas , un autómata finito no determinista con ε-transiciones (ε-NFA) se define como una tupla ( Q , Σ, δ , q 0 , F ) que consta de

Una palabra w ∈ Σ * se acepta como un ε-NCF si hay una cadena orientada desde un estado inicial q 0 a algún estado final F usando excavaciones desde δ tal que la concatenación de todas las etiquetas a lo largo del camino forma una palabra w . El conjunto de todas las palabras sobre Σ * aceptadas por el autómata es el lenguaje aceptado por el autómata A.

Si hablamos de un autómata finito no determinista A con un conjunto de estados Q como un gráfico dirigido, naturalmente nos referimos a un gráfico con un conjunto de vértices Q generado por transiciones. Ahora podemos enunciar el teorema.

Teorema de Eggan : la altura de iteración de un lenguaje regular L es igual al rango cíclico más pequeño entre todos los autómatas finitos no deterministas con transiciones ε que aceptan el lenguaje L.

La demostración de este teorema fue dada por Eggan [2] , y más tarde por Sakarovich [3] .

Problema generalizado de altura de iteración

La definición anterior asume que la expresión regular se basa en elementos del alfabeto A , utilizando únicamente las operaciones estándar de unión de conjuntos , concatenación y cierre de Kleene . Una expresión regular generalizada se define como una expresión regular, pero también incluye una operación de complemento conjunto (el complemento siempre se toma en relación con todas las palabras sobre A). Si asumimos que tomar relleno no aumenta la altura de la iteración, eso es

,

podemos definir la altura de iteración del lenguaje regular generalizado L como la altura de iteración mínima entre todas las expresiones regulares generalizadas que representan el lenguaje L .

Tenga en cuenta que mientras los idiomas con altura de iteración cero (ordinaria) contienen un número finito de palabras, hay infinitos idiomas con altura de iteración generalizada cero.

ejemplo _ Expresión regular

que vimos en el ejemplo anterior se puede reescribir de manera equivalente como una expresión regular generalizada

,

ya que el complemento del conjunto vacío son exactamente todas las palabras sobre el alfabeto A . Así, el conjunto de todas las palabras del alfabeto A que terminan en la letra a tiene una altura de iteración de uno, mientras que la altura de iteración generalizada es cero.

Los idiomas con altura de iteración cero se denominan idiomas sin asteriscos . Se puede demostrar que una lengua L es una lengua sin asteriscos si y sólo si su monoide sintáctico es aperiódico [4] .

Véase también

Notas

  1. ↑ Sakarovitch, 2009 , pág. 342.
  2. ↑ 12 Eggan , 1963 .
  3. ↑ 12 Sakarovitch , 2009 .
  4. ↑ Schützenberger, 1965 .

Literatura