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 símbolos de longitud infinita (específicamente, una secuencia de longitud ω) , y un lenguaje ω es un conjunto de palabras infinitas. Aquí, ω se refiere al primer número ordinal infinito , modelando un conjunto de números naturales .

Definicion formal

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 Σ. 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 ω, también pueden verse como funciones desde hasta Σ. El conjunto de todas las palabras infinitas sobre Σ se denota por Σ ^ω . El conjunto de todas las palabras finitas e infinitas sobre Σ a veces se escribe Σ ^∞ o Σ ^≤ω . ${\displaystyle \mathbb {N} }$

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

Operaciones

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 únicamente. Entonces K puede concatenarse a la izquierda, y sólo a la izquierda, con L para producir el nuevo lenguaje ω KL .

Omega (iteración infinita)

Como sugiere la notación, la operación 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 (\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 L de longitud finita , una palabra ω w está en el límite de L si y sólo 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 límite en L se puede escribir L ^δ o . ${\displaystyle {\vec {L}}}$

Distancia entre palabras ω

El conjunto Σ ^ω se puede convertir en un espacio métrico mediante la 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 mínimo sobre conjuntos de números reales . Si entonces no existe el prefijo x más largo y entonces . 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 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 de lenguas ω más utilizada es el conjunto de lenguas ω-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 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 del 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ática pura y aplicada Vol 141, Elsevier, 2004.
• Staiger, L. "Lenguas ω". 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, Handbook of Theoretical Computer Science , Volumen B: Modelos formales y semántica, páginas 133-192. Elsevier Science Publishers, Ámsterdam, 1990.