lenguaje omega

Sea Σ un conjunto de símbolos (no necesariamente finitos). Siguiendo la definición estándar de la teoría del lenguaje formal , Σ ^* es el conjunto de todas las palabras finitas sobre Σ. Toda 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} → Σ, con el valor en i dando el símbolo en la posición i . Las infinitas palabras, o ω-palabras, también pueden verse como funciones de a Σ. El conjunto de todas las palabras infinitas sobre Σ se denota Σ ^ω . El conjunto de todos los finitos y ${\ estilo de visualización \ mathbb {N}}$ infinitas palabras sobre Σ a veces se escribe Σ ^∞ .

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

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 entonces no hay un prefijo x más largo y así . La simetría es clara. La transitividad se deriva 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 los primeros caracteres de w y u deben ser iguales, por lo que . Por eso ${\ estilo de visualización w = v}$ ${\ estilo de visualización d (w, v) = 0}$ ${\ estilo de visualización \ min \ {m, n \}}$ $d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d( v,u)$ d es una métrica.

La subclase más utilizada de los lenguajes ω es el conjunto de lenguajes regulares ω , que disfrutan de la propiedad útil de ser reconocibles por los autómatas de Büchi . Por lo tanto, el problema de decisión de la pertenencia a un lenguaje regular ω es decidible utilizando un autómata de Büchi y bastante sencillo de calcular.

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