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 Σ ≤ω .
Por 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 .
- 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 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 .
Distancia entre palabras ω
El conjunto Σ ω puede convertirse en un espacio métrico por definición de la métrica como:
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.
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.