Linguagem ômega

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

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

Assim, uma linguagem linguagem-ω ${\displaystyle L}$ sobre ${\displaystyle \Sigma }$ é um subconjunto de ${\displaystyle \Sigma ^{\omega }}$.

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

Interseção e união

Dada linguagens-ω ${\displaystyle L}$ e ${\displaystyle M}$, ambas ${\displaystyle L\cup M}$ e ${\displaystyle L\cap M}$ são linguagens-ω.

Concatenação à esquerda

Seja ${\displaystyle L}$ uma linguagem-ω, e ${\displaystyle K}$ uma linguagem de palavras finitas apenas. Então ${\displaystyle K}$ pode somente ser concatenada à esquerda de ${\displaystyle L}$ para produzir a nova linguagem-ω ${\displaystyle KL}$.

Iteração infinita

A operação ${\displaystyle \bullet ^{\omega }}$ é a versão infinita do fecho de Kleene sobre linguagens de tamanho finito. Dada uma linguagem formal ${\displaystyle L}$, ${\displaystyle L^{\omega }}$ é a linguagem-ω de todas as sucessões infinitas de palavras de ${\displaystyle L}$. Numa visão funcional, todas as funções ${\displaystyle \mathbb {N} \to L}$.

Prefixos

Seja ${\displaystyle w}$ uma palavra-ω. Então, a linguagem formal ${\displaystyle \pi (w)}$ contém todo prefixo finito de ${\displaystyle w}$.

Limite

Dada uma linguagem de tamanho finito ${\displaystyle L}$, uma palavra-ω ${\displaystyle w}$ está no limite de ${\displaystyle L}$ se e somente se ${\displaystyle \pi (w)\cap L}$ é um conjunto infinito. Em outras palavras, para um número natural arbitrariamente grande ${\displaystyle n}$, é sempre possível escolher algum prefixo ${\displaystyle w}$ em ${\displaystyle L}$ cujo tamanho é maior do que ${\displaystyle n}$. A operação de limite sobre ${\displaystyle L}$ pode ser denotada ${\displaystyle L^{\delta }}$ ou ${\displaystyle {\vec {L}}}$.

O Conjunto ${\displaystyle \Sigma ^{\omega }}$ 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.

A mais usada subclasse das linguagens-ω é o conjunto de linguagens ω-regulares, que tem a útil propriedade de ser reconhecida pelo autômato 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.

• 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.