Lenguaje omega

Concepto teórico de informática

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

Definición formal

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} → Σ, con el valor en i dando el símbolo en la posición i . Las palabras infinitas, o ω-palabras, pueden verse asimismo como funciones de 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 Σ ^≤ω . ${\displaystyle \mathbb {N} }$

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

Operaciones

Algunas operaciones comunes definidas en los 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. Entonces K puede concatenarse por la izquierda, y solo por la izquierda, a L para obtener el nuevo lenguaje ω KL .

Omega (iteración infinita)

Como sugiere la notación, la operación es la versión infinita del operador de 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 visión funcional, de todas las funciones . ${\displaystyle (\cdot )^{\omega }}$ ${\displaystyle \mathbb {N} \to L}$

Prefijos

Sea w una palabra ω. Entonces, el lenguaje formal Pref( w ) contiene cada prefijo finito 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 arbitrariamente grande n , 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 puede escribirse L ^δ o . ${\displaystyle {\vec {L}}}$

Distancia entre palabras ω

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

${\displaystyle d(w,v)=\inf\{2^{-|x|}\mid x\in \Sigma ^{*}\ {\text{and}}\ 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 entonces no hay un prefijo más largo x y por lo tanto . 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 los primeros caracteres de w y u deben ser los mismos, por lo tanto . Por lo tanto, d es una métrica. ${\displaystyle w=v}$ ${\displaystyle d(w,v)=0}$ ${\displaystyle \min\{m,n\}}$ ${\displaystyle d(w,u)\leq 2^{-\min\{m,n\}}\leq 2^{-m}+2^{-n}=d(w,v)+d(v,u)}$

Subclases importantes

La subclase más utilizada de los lenguajes ω es el conjunto de lenguajes ω-regulares , que gozan de la útil propiedad 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 se puede decidir utilizando un autómata de Büchi y es bastante sencillo de calcular.

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 estudia en la verificación de modelos .

Bibliografía

• 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. "ω-Languages". 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 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.