Clase de ω-lenguajes que generalizan la definición de lenguajes regulares a infinitas palabras
Los lenguajes ω-regulares son una clase de ω-lenguajes que generalizan la definición de lenguajes regulares a infinitas palabras.
Definición formal
Un lenguaje ω L es ω-regular si tiene la forma
- A ω donde A es un lenguaje regular que no contiene la cadena vacía
- AB , la concatenación de un lenguaje regular A y un lenguaje ω-regular B (nótese que BA no está bien definido)
- A ∪ B donde A y B son lenguajes ω-regulares (esta regla solo se puede aplicar un número finito de veces)
Los elementos de A ω se obtienen concatenando palabras de A infinitas veces. Nótese que si A es regular, A ω no es necesariamente ω-regular, ya que A podría ser, por ejemplo, {ε}, el conjunto que contiene solo la cadena vacía , en cuyo caso A ω = A , que no es un lenguaje ω y, por lo tanto, no es un lenguaje ω-regular.
Una consecuencia directa de la definición es que los lenguajes ω-regulares son precisamente los lenguajes ω de la forma A 1 B 1 ω ∪ ... ∪ A n B n ω para algún n , donde los A i s y los B i s son lenguajes regulares y los B i s no contienen la cadena vacía.
Equivalencia con el autómata Büchi
Teorema : Un autómata Büchi reconoce un lenguaje ω si y sólo si es un lenguaje ω-regular.
Demostración : Todo lenguaje ω-regular es reconocido por un autómata Büchi no determinista; la traducción es constructiva. Utilizando las propiedades de clausura de los autómatas Büchi y la inducción estructural sobre la definición de lenguaje ω-regular, se puede demostrar fácilmente que se puede construir un autómata Büchi para cualquier lenguaje ω-regular dado.
Por el contrario, para un autómata Büchi dado A = ( Q , Σ, δ, I , F ) , construimos un lenguaje ω-regular y luego demostraremos que este lenguaje es reconocido por A . Para una ω-palabra w = a 1 a 2 ... sea w ( i , j ) el segmento finito a i +1 ... a j -1 a j de w . Para cada q , q' ∈ Q , definimos un lenguaje regular L q,q' que es aceptado por el autómata finito ( Q , Σ, δ , q , { q' }) .
- Lema: Afirmamos que el autómata Büchi A reconoce el lenguaje ⋃ q ∈ I , q '∈ F L q,q' ( L q',q' − { ε } ) ω .
- Demostración: Supongamos que la palabra w ∈ L ( A ) y q 0 , q 1 , q 2 ,... es una serie aceptante de A en w . Por lo tanto, q 0 está en I y debe haber un estado q' en F tal que q' ocurra infinitamente a menudo en la serie aceptante. Elijamos la secuencia infinita estrictamente creciente de índices i 0 , i 1 , i 2 ... tal que, para todo k ≥0, q i k es q' . Por lo tanto, w (0, i 0 )∈ L q 0 , q' y, para todo k ≥0, w ( i k , i k +1 )∈ L q',q' . Por lo tanto, w ∈ L q 0 ,q' ( L q',q' ) ω .
- Por el contrario, supongamos que w ∈ L q,q' ( L q',q' − { ε } ) ω para algún q ∈ I y q '∈ F . Por lo tanto, existe una secuencia infinita y estrictamente creciente i 0 , i 1 , i 2 ... tal que w (0, i 0 ) ∈ L q,q' y, para todo k ≥0, w ( i k , i k +1 )∈ L q',q' . Por definición de L q,q' , existe una serie finita de A desde q hasta q' en la palabra w (0, i 0 ). Para todo k ≥0, existe una serie finita de A desde q' hasta q' en la palabra w ( i k , i k +1 ). Por esta construcción, existe una serie de A que comienza en q y en la que q' aparece infinitamente a menudo. Por lo tanto, w ∈ L ( A ) .
Equivalencia con la lógica monádica de segundo orden
Büchi demostró en 1962 que los lenguajes ω-regulares son precisamente los definibles en una lógica monádica de segundo orden particular llamada S1S.
Bibliografía
- Wolfgang Thomas, "Autómatas en objetos infinitos". En Jan van Leeuwen , editor, Handbook of Theoretical Computer Science, volumen B: Formal Models and Semantics , páginas 133-192. Elsevier Science Publishers, Ámsterdam, 1990.
