Linguagem ômega – Wikipédia, a enciclopédia livre
Esta página ou seção carece de contexto.Dezembro de 2011) ( |
Uma linguagem-ω é um conjunto de sequências de tamanho infinito de símbolos.
Definição formal
[editar | editar código-fonte]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 | editar código-fonte]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 ()ω é 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 | editar código-fonte]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 | editar código-fonte]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 | editar código-fonte]- 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.