Linguagem ômega

Uma linguagem-ω é um conjunto de sequências de tamanho infinito de símbolos.

Definição formal

Seja Σ um conjunto de símbolos (não necessariamente finito). Seguindo a definição padrão da teoria da linguagem formal, Σ^* é o conjunto de todas as palavras finitas sobre Σ. Toda palavra finita tem um tamanho, que é, obviamente, uma número natural. Dada uma palavra w de tamanho n , w pode ser vista como uma função do conjunto {0,1,...,n-1} → Σ. As palavras infinitas, ou palavras-ω, podem também ser vistas como funções de $\mathbb {N}$ para Σ, com o valor de i dando o símbolo na posição i. O conjunto de todas as palavras infinitas sobre Σ é chamado de Σ^ω. O conjunto de todas as palavras finitas e infinitas sobre Σ é algumas vezes escrito como Σ^∞.

Assim, uma linguagem linguagem-ω L sobre Σ é um subconjunto de Σ^ω.

Operações

Algumas operações comuns definidas em linguagens-ω são:

• Interseção e União. Dada linguagens-ω L e M, ambas L ∪ M e L ∩ M são linguagens-ω.
• Concatenação a esquerda. Seja L uma linguagem-ω, e K uma linguagem de palavras finitas apenas. Então K pode somente ser concatenada a esquerda de L para produzir a nova linguagem-ω KL.
• Omega (iteração infinita). Como a notação diz, a operação ($\cdot$)^ω é a versão infinita do operador Fecho de Kleene sobre linguagens de tamanho finito. Dada uma linguagem formal L, L^ω é a linguagem-ω de todas as sequências infinitas de palavras de L; numa visão funcional, todas as funções $\mathbb {N}$→L.
• Prefixos. Seja w uma palavra-ω. Então a linguagem formal Pref(w) contém todo prefixo finito de w.
• Limite. Dada uma linguagem de tamanho finito L, uma palavra-ω w está no limite de L se e somente se Pref(w) ∩ L é um conjunto infinito. Em outras palavras, para um numero natural grande arbitrário n, é sempre possívl escolher alguma palavra em L cujo tamanho é maior do que n, e que é um prefixo de w. A operação de limite sobre L pode ser escrita L^δ ou ${\vec {L}}$.

Distância entre palavras-ω

O Conjunto Σ^ω pode ser transformado num espaço métrico por definição da métrica d:Σ^ω × Σ^ω → R desta forma:

Se w e v compartilham algum prefixo finito, então d(w,v)= inf {2^-|x| : x em Σ^*, e x em ambos Pref(w) e Pref(v) }.

Senão d(w, v)=1

onde |x| é interpretado como "o tamanho de x" (numero de símbolos em x), e inf é o mínimo sobre conjuntos de números reais. Se w=v, eles não tem nenhum prefixo finito maior do que o outro, e d(w,v)=0; pode ser mostrado que d satisfaz todas as outras propriedades necessárias de uma métrica.

Subclasses importantes

A mais usada subclasse das linguagens-ω é o conjunto de linguagens ω-regulares, que tem a útil propriedade de ser reconhecida pelo automato de Büchi; assim o problema de decisão de se é uma linguagem ω-regular ou não é decidível e bem simples de ser computado.

Bibliografia

• Perrin, D. and Pin, J-E. "Infinite Words Automata, Semigroups, Logic and Games". Pure and Applied Mathematics Vol 141, Elsevier, 2004.
• Staiger, L. "ω-Languages". Em G. Rozenberg and A. Salomaa, editores, Handbook of Formal Languages, Volume 3, páginas 339-387. Springer-Verlag, Berlin, 1997.
• Thomas, W. "Automata on Infinite Objects". Em Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, páginas 133-192. Elsevier Science Publishers, Amsterdam, 1990.