Los ω-lenguajes regulares son una clase de ω-lenguajes que generalizan la definición de lenguajes regulares a infinitas palabras. Büchi mostró en 1962 que los lenguajes ω-regulares son precisamente los definibles en una lógica monádica particular de segundo orden llamada S1S.
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 {ε}, el conjunto que contiene solo la cadena vacía , en cuyo caso A ω = A , que no es un lenguaje ω y por lo tanto no un lenguaje ω-regular.
Teorema : un autómata de Büchi reconoce un lenguaje ω si y solo si es un lenguaje regular ω.
Prueba : Todo lenguaje ω-regular es reconocido por un autómata Büchi no determinista; la traducción es constructiva. Usando 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 dado.
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 todo q , q' ∈ Q , definimos un lenguaje regular L q,q' que es aceptado por el autómata finito ( Q , Σ, δ , q , { q' }) .