Linguagem ômega
# 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.