stringtranslate.com

Lenguaje omega-regular

Los lenguajes ω-regulares son una clase de lenguajes ω que generalizan la definición de lenguajes regulares a infinitas palabras.


Definicion formal

Un lenguaje ω L es ω-regular si tiene la forma

Los elementos de A ω se obtienen concatenando palabras de A infinitas veces. Tenga en cuenta 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.

Es una consecuencia directa de la definición de que los lenguajes ω-regulares son precisamente los lenguajes ω de la forma A 1 B 1 ω ∪ ... ∪ A n B n ω para algún n , donde A i s y B i Los s son lenguajes regulares y los B i s no contienen la cadena vacía.

Equivalencia al autómata Büchi

Teorema : Un autómata de Büchi reconoce un lenguaje ω si y solo si es un lenguaje ω-regular.

Prueba : Cada lenguaje ω-regular es reconocido por un autómata Büchi no determinista; La traducción es constructiva. Utilizando las propiedades de cierre de los autómatas de 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 de Büchi para cualquier lenguaje ω-regular determinado.

Por el contrario, para un autómata Büchi dado A = ( Q , Σ, δ, I , F ) , construimos un lenguaje ω-regular y luego mostraremos 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' − { ε } ) ω .
Prueba: Supongamos que la palabra w ∈ L ( A ) y q 0 , q 1 , q 2 ,... es una ejecución de aceptación 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 ejecución de aceptación. Escojamos 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 w ∈ L q,q' ( L q',q' − { ε } ) ω para algunos 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' , hay una ejecución finita de A desde q hasta q' en la palabra w (0, i 0 ). Para todo k ≥0, hay una ejecución finita de A desde q' hasta q' en la palabra w ( i k , i k +1 ). Según esta construcción, hay una serie de A , que comienza desde q y en la que q' ocurre infinitamente. Por tanto, w ∈ L ( A ) .

Equivalencia a 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 particular de segundo orden llamada S1S.

Bibliografía