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

Definição formal

editar

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

editar

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

  • Interseção e União. Dada linguagens-ω L e M, ambas LM e LM 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 ( )ω é 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  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  .

Distância entre palavras-ω

editar

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

editar

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

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