Lenguaje Omega

En la teoría del lenguaje formal dentro de la informática teórica , un lenguaje ω es un conjunto de palabras infinitas, donde una palabra infinita es una secuencia de longitud infinita (específicamente, una secuencia de longitud ω) de símbolos . Aquí, ω se refiere al primer número ordinal infinito , que modela un conjunto de números naturales .

Sea Σ un conjunto de símbolos (no necesariamente finito). Siguiendo la definición estándar de la teoría del lenguaje formal , Σ ^* es el conjunto de todas las palabras finitas sobre Σ. Cada palabra finita tiene una longitud, que es un número natural. Dada una palabra w de longitud n , w puede verse como una función del conjunto {0,1,..., n − 1} → Σ, donde el valor en i da el símbolo en la posición i . Las palabras infinitas, o ω-palabras, pueden verse de manera similar como funciones de${\displaystyle \mathbb {N} }$a Σ. El conjunto de todas las palabras infinitas sobre Σ se denota Σ ^ω . El conjunto de todas las palabras finitas e infinitas sobre Σ a veces se escribe Σ ^∞ o Σ ^≤ω .

Por tanto, un lenguaje ω L sobre Σ es un subconjunto de Σ ^ω .

Algunas operaciones comunes definidas en lenguajes ω son:

Intersección y unión

Dados los ω-lenguajes L y M , tanto L ∪ M como L ∩ M son ω-lenguajes.

concatenación izquierda

Sea L un ω-lenguaje y K un lenguaje de palabras finitas solamente. Entonces K puede concatenarse por la izquierda, y solo por la izquierda, a L para producir el nuevo ω-lenguaje KL .

Omega (iteración infinita)

Como sugiere la notación, la operación${\displaystyle (\cdot )^{\omega }}$es la versión infinita del operador estrella de Kleene en lenguajes de longitud finita. Dado un lenguaje formal L , L ^ω es el ω-lenguaje de todas las secuencias infinitas de palabras de L ; en la vista funcional, de todas las funciones${\displaystyle \mathbb {N} \to L}$.

Prefijos

Sea w una palabra ω. Entonces el lenguaje formal Pref( w ) contiene todos los prefijos finitos de w .

Límite

Dado un lenguaje de longitud finita L , una ω-palabra w está en el límite de L si y solo si Pref( w ) ∩ L es un conjunto infinito . En otras palabras, para un número natural n arbitrariamente grande , siempre es posible elegir alguna palabra en L , cuya longitud sea mayor que n , y que sea un prefijo de w . La operación de límite en L se puede escribir L ^δ o${\displaystyle {\vec {L}}}$.

El conjunto Σ ^ω puede convertirse en un espacio métrico por definición de la métrica.${\displaystyle d:\Sigma ^{\omega }\times \Sigma ^{\omega }\rightarrow \mathbb {R} }$como:

${\displaystyle d(w,v)=\inf\{2^{-|x|}\mid x\in \Sigma ^{*}\ {\text{y}}\ x\in {\text{Pref}}(w)\cap {\text{Pref}}(v)\}}$

donde | x | se interpreta como "la longitud de x " (número de símbolos en x ), e inf es el ínfimo sobre conjuntos de números reales . Si${\displaystyle w=v}$entonces no hay prefijo más largo x y así${\displaystyle d(w,v)=0}$La simetría es clara. La transitividad se deduce del hecho de que si w y v tienen un prefijo compartido máximo de longitud m y v y u tienen un prefijo compartido máximo de longitud n, entonces el primero${\displaystyle \min\{m,n\}}$Los caracteres de w y u deben ser iguales, por lo tanto${\displaystyle d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)}$Por lo tanto, d es una métrica.

La subclase más utilizada de los lenguajes ω es el conjunto de lenguajes ω -regulares , que poseen la útil propiedad de ser reconocibles por autómatas de Büchi . Por lo tanto, el problema de decisión sobre la pertenencia a un lenguaje ω-regular se puede resolver mediante un autómata de Büchi y su cálculo es bastante sencillo.

Si el lenguaje Σ es el conjunto potencia de un conjunto (llamado "proposiciones atómicas") entonces el lenguaje ω es una propiedad de tiempo lineal , que se estudian en la verificación de modelos .

• Perrin, D. y Pin, J.-E. " Palabras infinitas: autómatas, semigrupos, lógica y juegos ". Matemáticas puras y aplicadas, vol. 141, Elsevier, 2004.
• Staiger, L. " ω -Lenguajes ". En G. Rozenberg y A. Salomaa , editores, Handbook of Formal Languages , Volumen 3, páginas 339-387. Springer-Verlag, Berlín, 1997.
• Thomas, W. «Autómatas sobre objetos infinitos». En Jan van Leeuwen , editor, Manual de informática teórica , Volumen B: Modelos formales y semántica, páginas 133-192. Elsevier Science Publishers, Ámsterdam, 1990.