ads:
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE TECNOLOGIA E GEOCIÊNCIAS
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
DANIEL PEDRO BEZERRA CHAVES
REPRESENTAÇÃO DE SISTEMAS
DINÂMICOS SIMBÓLICOS DE
MEMÓRIA FINITA USANDO GRAFOS
RECIFE, SETEMBRO DE 2006.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
DANIEL PEDRO BEZERRA CHAVES
REPRESENTAÇÃO DE SISTEMAS
DINÂMICOS SIMBÓLICOS DE
MEMÓRIA FINITA USANDO GRAFOS
Dissertação submetida ao Programa de Pós-
Graduação em Engenharia Elétrica da Universi-
dade Federal de Pernambuco como parte dos re-
quisitos para obtenção do grau de Mestre em
Engenharia Elétrica
ORIENTADOR: PROF. CECILIO JOSÉ LINS PIMENTEL, PH.D.
Recife, Setembro de 2006.
c
Daniel Pedro Bezerra Chaves, 2006
ads:
UNIVERSIDADE FEDERAL DE PERNAMBUCO
CENTRO DE TECNOLOGIA E GEOCIÊNCIAS
PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA
Daniel Pedro Bezerra Chaves
Representação de Sistemas Dinâmicos Simbólicos de
Memória Finita Usando Grafos
‘Esta Dissertação foi julgada adequada para
obtenção do Título de Mestre em Engenharia
Elétrica, Área de Concentração em Comuni-
cações, e aprovada em sua forma final pelo Pro-
grama de Pós-Graduação em Engenharia Elétrica
da Universidade Federal de Pernambuco’.
Prof. Joaquim Ferreira Martins Filho, Ph.D.
Coordenador do Programa de
Pós-graduação em Engenharia Elétrica
Banca Examinadora:
Prof. Cecilio José Lins Pimentel, Ph.D.
Orientador
Universidade Federal de Pernambuco
Prof. Ricardo Menezes Campello de Souza, Ph.D.
Universidade Federal de Pernambuco
Prof. Reginaldo Palazzo Júnior, Ph.D.
Universidade Estadual de Campinas
18 de Setembro de 2006
Aos meus pais e irmãs
DEDICO
AGRADECIMENTOS
A Deus pela oportunidade de aprender.
Aos meus pais pelo apoio constante e incondicional.
Ao Prof. Dr. Cecilio Pimentel pela convivência enriquecedora, confiança no trabalho realizado e
orientação.
Aos Professores do DES-UFPE, principalmente aos do CODEC, pela disposição de dividirem seus
conhecimentos conosco.
À comissão julgadora pela atenção despendida ao trabalho.
Aos amigos com os quais convivi durante o Programa de Mestrado em Engenharia Elétrica.
Ao Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) pelo apoio financeiro
(Processo 134157/2004-4) concedido durante o período de outubro de 2004 a outubro de 2006, sem
o qual não seria possível a realização do Programa de Mestrado em Engenharia Elétrica.
DANIEL PEDRO BEZERRA CHAVES
Universidade Federal de Pernambuco
18 de Setembro de 2006
Resumo da Dissertação apresentada à UFPE como parte dos requisitos necessários para a obtenção
do grau de Mestre em Engenharia Elétrica
REPRESENTAÇÃO DE SISTEMAS DINÂMICOS
SIMBÓLICOS DE MEMÓRIA FINITA USANDO
GRAFOS
Daniel Pedro Bezerra Chaves
Setembro/2006
Orientador: Prof. Cecilio José Lins Pimentel, Ph.D.
Área de Concentração: Comunicações
Palavras-chaves: dinâmica simbólica, grafos direcionados, autômatos, códigos de linha, sistemas
com restrição
Número de páginas: 74
Nesta dissertação empregamos a teoria de dinâmica simbólica como ferramenta matemática para
abordar o problema da representação de seqüências de símbolos que podem ser modeladas por sis-
temas dinâmicos simbólicos de memória finita. Utilizando teoria de autômatos, apresentamos novos
algoritmos para gerar grafos determinísticos com um número mínimo de vértices que apresentam
a linguagem de um sistema dinâmico simbólico de memória finita. Para isto, definimos um novo
método, empregando fundamentos da teoria algébrica de linguagem, para determinar as classes da
relação de equivalência ρ de Myhill-Nerode sobre a linguagem do sistema dinâmico simbólico de
memória finita. A linguagem de um sistema dinâmico simbólico de memória finita é regular e, por-
tando, o conjunto das classes de equivalência de ρ é finito. Estas classes são interpretadas como os
vértices do grafo determinístico com um número mínimo de vértices que apresenta a linguagem.
O método apresentado é estendido para sistemas dinâmicos simbólicos de memória finita pe-
riódicos, que formam a classe (na teoria de dinâmica simbólica) utilizada para modelar conjuntos de
seqüências com restrição empregadas tanto para correção de erros quanto para codificação de linha.
Abstract of Dissertation presented to UFPE as a partial fulfillment of the requirements for the degree
of Master in Electrical Engineering
REPRESENTATIONS OF SHIFTS OF FINITE TYPE
USING GRAPHS
Daniel Pedro Bezerra Chaves
September/2006
Supervisor: Prof. Cecilio José Lins Pimentel, Ph.D.
Area of Concentration: Communication
Keywords: symbolic dynamics, directed graphs, automata, line codes, constrained systems
Number of pages: 74
Symbolic dynamics is commonly applied as a mathematical tool for studying the presentation of
sequences that form a shift of finite type. A new algorithm is proposed to generate the minimal
synchronizing and deterministic presentation of a shift of finite type, based on algebraic language
theory. The main idea is to determine the elements in a subset of the language of a shift of finite type
that belong to the same equivalence classes of the Myhill-Nerode relation ρ. Since the language of a
shift of finite type is regular, then ρ has a finite number of equivalence classes. These classes are the
vertices of the proposed graph construction.
The proposed method is extended for periodic shifts of finite type, which is the symbolic dynam-
ical system applied to study sets of sequences that have both error control and line coding properties.
LISTA DE FIGURAS
1.1 Diagrama em blocos de um sistema de comunicação incluindo os blocos dos códigos
CCE e restritivo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Grafo apresentando a restrição (d, k)-RLL. . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Restrição anti-tom: satisfaz a restrição (1, 3)-RLL e limita o número máximo de
repetições de “10” ou “01”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Organização da seqüência de dígitos gravada em um dispositivo de armazenamento
de dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Grafo apresentando a restrição (2, 18, 2)-RLL. . . . . . . . . . . . . . . . . . . . . . 15
1.6 Grafo da restrição espectro limitado dc-free. . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Autômato finito. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2 Linguagem ∅. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Linguagem {ε}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Linguagem {a}. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Apresentação do SSR par. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1 Grafo obtido da Tabela 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 Componente essencial do grafo apresentado na Figura 3.1. . . . . . . . . . . . . . . 47
3.3 Árvore para o cálculo do conjunto
˜
C
r
O
(101). . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Árvore para o cálculo das classes de equivalência. . . . . . . . . . . . . . . . . . . . 50
4.1 Diagrama de concatenação reversa. . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Diagrama de concatenação Wijngaarden-Immink. . . . . . . . . . . . . . . . . . . . 54
4.3 Apresentação de um PFT satisfazendo a restrição MTR(3) com T = 3 e U = {1}. . . 67
LISTA DE TABELAS
3.1 Descrição do Algoritmo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Cálculo das classes de equivalência e da função δ(C
i
, a), para C
i
∈ P e a ∈ A. . . . 44
3.3 Cálculo da função de transição δ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1 Cálculo das classes de equivalência e da função δ para o PFT do Exemplo 4.6. . . . . 68
SUMÁRIO
1 INTRODUÇÃO 11
1.1 Algumas Aplicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Dinâmica Simbólica e Teoria de Autômatos: Aspectos Gerais . . . . . . . . . . . . 17
1.3 Objetivos da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 AUTÔMATO, DINÂMICA SIMBÓLICA E GRAFO: CONCEITOS E RELAÇÕES 19
2.1 Teoria de Autômatos: alfabeto, palavras e linguagem . . . . . . . . . . . . . . . . 19
2.2 Dinâmica Simbólica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Autômato: Linguagem Regular . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4 Sistemas Simbólicos Fechados de Memória Finita (SFT) . . . . . . . . . . . . . . . 33
3 ALGORITMO PARA DETERMINAÇÃO DO CONTEXTO À DIREITA: APLICAÇÃO NA
CONSTRUÇÃO DA m-SDP 35
3.1 Alguns Conceitos e Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 Determinação de palavras com o mesmo contexto à direita . . . . . . . . . . . . . 39
3.3 Construção da m-SDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Análise da complexidade do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 47
3.4.1 Complexidade do Cálculo do Conjunto P . . . . . . . . . . . . . . . . . . . . 48
3.4.2 Complexidade do Cálculo da Função de Transição . . . . . . . . . . . . . . . 49
3.4.3 Complexidade do Algoritmo para Determinação da m-SDP . . . . . . . . . . 51
4 DETERMINAÇÃO DO CONTEXTO À DIREITA PARA PFT IRREDUTÍVEL: APLICAÇÃO
NA CONSTRUÇÃO DE APRESENTAÇÕES DETERMINÍSTICAS E REDUZIDAS 52
4.1 Alguns Conceitos e Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Determinação de palavras com mesmo contexto à direita . . . . . . . . . . . . . . 58
4.3 Construção de uma apresentação reduzida . . . . . . . . . . . . . . . . . . . . . . 62
4.4 Sistemas restritos com posições irrestritas . . . . . . . . . . . . . . . . . . . . . . . 65
5 CONCLUSÕES 69
5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
CAPÍTULO 1
INTRODUÇÃO
Em um sistema de comunicações, a informação é transmitida entre pontos do espaço através de
um canal de comunicações. Exemplos de áreas de aplicação da engenharia de telecomunicações nas
quais esta visão de canal é realçada são os sistemas de comunicação espacial e sistemas telefônicos
fixos e móveis. No entanto, sistemas de armazenamento de informação, como DVD e pen-drive, tam-
bém são interpretados como canais. A principal diferença entre canais de transmissão de informação
e canais de armazenamento de informação é que o conceito de espaço é substituído pelo de tempo.
Em sistemas de armazenamento, a informação é gravada em um ponto do tempo e acessada em um
ponto posterior.
Aplicações atuais de sistemas de armazenamento requerem boa imunidade contra erro [1]. Uma
das dificuldades para obtenção deste objetivo é a crescente demanda por maiores capacidades de
armazenamento de informação, que propicia o desenvolvimento de dispositivos hábeis a armazenar
mais dados por unidade de área, tornando a ação de leitura e escrita dos dados menos confiável. Esta
complicação deve-se aos efeitos de interferência inter-simbólica, imprecisão do relógio e ruído.
Codificadores restritivos
, também conhecidos como
codificadores moduladores
ou
codificadores
de linha
, convertem seqüências arbitrárias em seqüências satisfazendo uma dada restrição. De forma
geral, o objetivo de um código restritivo é melhorar o desempenho do sistema de comunicação adap-
tando a seqüência de dados às características do canal.
Além dos códigos restritivos, também são empregados os códigos corretores de erros (CCE).
Um dos principais critérios de projeto de um CCE consiste na maximização da distância mínima
do código, permitindo que a palavra-código transmitida possa ser recuperada a partir de sua versão
corrompida pelo ruído do canal. Assim, como diferença entre CCE e códigos restritivos, podemos
dizer que enquanto no primeiro procura-se aumentar a distância mínima do código (característica
do conjunto de palavras-código), no segundo a suscetibilidade das palavras-código de serem cor-
rompidas ao passarem pelo canal deve ser minimizada (característica de cada palavra-código). Esta
diferença é relativa, já que o conjunto de palavras código de um CCE não pode ser completamente
arbitrário e também apresenta restrições. Isto aumenta o interesse em códigos restritivos que também
possuam propriedades de correção de erros, o que vem ampliando a região de interseção entre estas
duas classes, sem no entanto eliminar as peculiaridades concernentes a cada tipo de código, no que
se refere aos fundamentos e problemas fundamentais de cada um deles.
Codificador
CCE
Codificador
restritivo
Decodificador
restritivo
Decodificador
CCE
m
Canal
m
′
Figura 1.1: Diagrama em blocos de um sistema de comunicação incluindo os blocos dos códigos CCE e
restritivo.
A Figura 1.1 mostra o diagrama em blocos da parte de um sistema de comunicações relevante
para este trabalho. A mensagem m passa pelo codificador CCE e em seguida pelo codificador res-
tritivo. Na recepção, a mensagem recebida é processada por dois blocos decodificadores, gerando a
mensagem decodificada m
′
. Se a ordem de codificação fosse invertida, o codificador CCE poderia
destruir a restrição gerada pelo codificador restritivo. Mas o código restritivo pode alterar as carac-
terísticas para as quais o CCE foi projetado, reduzindo sua eficácia. Tentando contornar este dilema,
há técnicas que propõem um diagrama em blocos com um codificador CCE sistemático posposto ao
codificador restritivo, associado a um procedimento para inserção dos dígitos de paridade na seqüên-
cia dos dígitos de informação sem que a restrição seja violada, assunto que será tratado no Capítulo 4.
Atualmente, alguns trabalhos apresentam técnicas de codificação que permitem tanto a correção de
erros como a geração de seqüências restritas de forma integrada [2], [3], [4].
1.1 Algumas Aplicações
Nesta seção são apresentadas algumas seqüências restritas empregadas em dispositivos comerci-
ais de forma isolada ou combinadas.
12
Restrição RLL
Seqüências que satisfazem a restrição (d, k)-RLL ((d, k)-runlength-limited), com d e k inteiros
tais que 0 ≤ d ≤ k, não possuem seqüências de zeros consecutivos de comprimento maior que
k (restrição-k) e seqüências de zeros consecutivos entre uns possuem comprimento pelo menos
d (restrição-d). Nas aplicações, a restrição-d reduz o efeito da interferência inter-simbólica e a
restrição-k melhora o controle da sincronização de relógio. Entre as seqüências (d, k)-RLL comer-
ciais estão a (1, 3)-RLL, empregada em drivers para discos magnéticos flexíveis, e a (2, 10)-RLL,
empregada em drivers para CD e DVD [5].
Todas as seqüências satisfazendo uma restrição (d, k)-RLL podem ser descritas pela leitura dos
rótulos de caminhos em um grafo direcionado, rotulado e finito como apresentado na Figura 1.2.
0 1
d
d + 1 k − 1
k
0
0
0 0
0
0 0
1
1 1
1
Figura 1.2: Grafo apresentando a restrição (d, k)-RLL.
Como descrição alternativa, poderíamos especificar um conjunto de seqüências proibidas F, tal
que, para qualquer seqüência a
1
a
2
. . . a
n
se a
i
. . . a
j
/∈ F, 1 ≤ i ≤ j ≤ n, então a
1
a
2
. . . a
n
satisfaz
a restrição (d, k)-RLL. Para d > 0 e k < ∞ o conjunto proibido é:
F = {11 , 101, . . . , 10 . . . 0
(d−1)
1, 00 . . . 0
(k+1)
}
Restrição anti-tom
Há aplicações que impõem um limite máximo para o comprimento de seqüências periódicas. Da
analogia com um sinal periódico decorre o nome dado a esta restrição.
Como exemplo, enquanto na restrição RLL o parâmetro k limita o comprimento máximo da
seqüência de período um 000 . . ., poderia ser de justificativa prática limitar o comprimento máximo
de seqüências de período dois, como 101010 . . . ou 010101 . . ..
A restrição de seqüênciascomunidadeperiódica 10 e 01 têm sido empregada em algumas versões
de canais sem fio por infravermelho para troca de dados entre dispositivos móveis, como computa-
dores portáteis. A seqüência de bits é convertida em uma seqüência de pulsos, na qual o bit “1” é
13
representado pela presença de pulso e o bit “0” pela ausência de pulso. Quanto maior o ciclo de
trabalho de uma seqüência (número de ocorrências de uns dividido pelo comprimento da seqüência)
maior o número de pulsos transmitidos por unidade de tempo. Assim, para limitar a potência trans-
mitida, seqüências com alto ciclo de trabalho são restringidas. Na Figura 1.3 apresentamos um grafo
que satisfaz simultaneamente a restrição (1, 3)-RLL e limita a dois o número máximo de ocorrências
de “10” ou “01”, sendo o conjunto proibido F = {11, 0000, 10101}.
0 1 2 3
a
b
0
1
00 0
0
1 1
Figura 1.3: Restrição anti-tom: satisfaz a restrição (1, 3)-RLL e limita o número máximo de repetições de “10”
ou “01”.
A restrição (d, k)-RLL é imposta para reduzir a interferência inter-simbólica e melhorar o sincro-
nismo. Se esta restrição for (1, k)-RLL, então ciclos de trabalho máximo (aproximadamente 50%) só
são alcançados pelas seqüências 0 101 . . . e 1010 . . .. Assim, limitar tais seqüências pode ser útil em
algumas aplicações, e.g., o padrão Very Fast Infrared adotado pela Infrared Data Association (IrDA-
VFIr) que inclui como parte do formato uma restrição que simultaneamente satisfaz a (1 , 13)-RLL
e limita o número máximo de repetições de “10” ou “01” a cinco [6]. A restrição anti-tom também
tem sido aplicada para melhorar a temporização e algoritmos de controle de ganho em sistemas de
gravação magnética [4].
Restrição para sincronização
Há aplicações onde a restrição é definida por um conjunto de palavras proibidas sobre um al-
fabeto, comum em sistemas que empregam marcadores. Tais restrições podem ser úteis para sin-
cronização, procedimento comum em sistemas de armazenamento, onde os dados são agrupados em
setores. Para acessar os dados em um setor, a cabeça de leitura deve ser posicionada no início deste.
No entanto, tanto o posicionamento preciso no primeiro bit de um setor, como a possível perda de
sincronismo na execução do posicionamento, são dificuldades técnicas a serem contornadas. Para
redução destas dificuldades, os setores são antecedidos por seqüências reservadas (não ocorrem den-
tro dos setores), que auxiliam na rápida sincronização do relógio, permitindo a determinação do
14
início dos dados codificados. A este conjunto de palavras reservadas dar-se-á o nome de marca de
sincronização ou sync mark (ver Figura 1.4).
Sync
Mark
Dados
Codificados
Sync
Mark
Dados
Codificados
Sync
Mark
Dados
Codificados
Figura 1.4: Organização da seqüência de dígitos gravada em um dispositivo de armazenamento de dados.
O posicionamento das marcas de sincronização é determinado pela correlação das seqüências
de entrada com as marcas de sincronização. Caso uma marca de sincronização pudesse ocorrer na
seqüência de dados, a leitura de uma falsa marca poderia levar a uma decodificação errada. Assim,
a codificação dos dados deve gerar seqüências em que não ocorram marcas de sincronização, como
também as seqüências mais prováveis geradas pela ação do ruído sobre a marca de sincronização.
Como exemplo, consideremos o conjunto de quatro palavras de comprimento 24 cada: 010w
0
01w
1
, 010w
0
10w
1
, 001w
0
01w
1
e 001w
0
10w
1
, onde w
0
= 000000 e w
1
= 0101010 101010. Uti-
lizadas em um sistema magnético [4], a primeira destas seqüências foi utilizada como marca de
sincronização e as outras são as seqüências mais prováveis de ocorrer pela ação do ruído sobre a
primeira. Nestes sistemas as restrições (1, 7)-RLL e anti-tom também foram empregadas.
Restrição RLL multi-espaçada
Esta restrição constitui uma variante da (d, k)-RLL, caracterizada pelos parâmetros (d, k, s),
onde d e k determinam o número mínimo e máximo de zeros entre uns consecutivos, respectiva-
mente. O parâmetro s indica que o número de zeros entre uns consecutivos deve ser um múltiplo de
s, e.g., se s = 2 toda seqüência de zeros tem comprimento par. Na Figura 1.5 temos o grafo que
apresenta a restrição (2, 18, 2)-RLL.
0 1 2 3 4 15 16 17 18
00 0
0 0
0 0 0
1 11 1
0 0
Figura 1.5: Grafo apresentando a restrição (2, 18, 2)-RLL.
As restrições (d, k, 2)-RLL foram inicialmente investigadas no contexto de gravação magnética
15
[7]. Recentemente foi mostrado que as restrições (d, k, 2)-RLL desempenham um papel natural em
sistemas de gravação óptico-magnético [4], tendo a IBM desenvolvido um protótipo deste sistema
que emprega a restrição (2, 18, 2)-RLL.
Restrição espectro limitado
Algumas restrições são definidas sobre um alfabeto bipolar {+1, −1}. Este alfabeto é direta-
mente associado a polaridade do sinal gravado ou transmitido, o que é enfatizado pela denominação
seqüência de polaridades
, empregada para enfatizar essa associação.
Um sistema restrito de seqüências bipolares tem
espectro limitado
em uma dada freqüência (nor-
malizada) f = m/n, se existe uma constante B, tal que, para toda seqüência w = w
0
w
1
. . . w
ℓ−1
que satisfaz a restrição do sistema e qualquer 0 ≤ i ≤ i
′
< ℓ, tem-se
i
′
s=i
w
s
e
− 2πs
m
n
≤ B, (1.1)
onde =
√
−1 [8] (a freqüência real é dada por f/T , sendo T o período de um bit).
Seqüências com espectro limitado em f = 0, chamadas dc-free ou de conteúdo limitado, vêm
sendo empregadas em sistemas de gravação magnética. Restrições relacionadas são impostas a sis-
temas de gravação óptica para reduzir interações entre os dados gravados e o sistema de gravação,
como também para filtragem de ruídos de baixa freqüência resultantes de marcas digitais [4]. A
restrição dc-free também é usada em sistemas de comunicação onde sinais de baixa freqüência são
susceptíveis à distorção, o que inclui linhas de transmissão via cabo e fibra óptica.
Para f = 0, o valor máximo do módulo do somatório da Equação 1.1 é chamado de DSV (do
inglês digital sum variation) da seqüência. O conjunto de todas as seqüências com DSV limitado
a B é um sistema restrito apresentado pelo grafo da Figura 1.6. Para uma restrição dc-free, quanto
maior o valor de B menor será a redução causada nas componentes espectrais próximas a f = 0.
Esta restrição é um exemplo em que o conjunto proibido não é finito.
0 1 2
B
+1
−1
+1
−1
−1
+1
−1
+1
Figura 1.6: Grafo da restrição espectro limitado dc-free.
16
1.2 Dinâmica Simbólica e Teoria de Autômatos: Aspectos Gerais
Nesta seção enfocamos a motivação que levou ao desenvolvimento da teoria de dinâmica sim-
bólica e de autômatos e o contexto da aplicação destas à teoria de códigos.
Dinâmica Simbólica
Dinâmica Simbólica faz parte da teoria de sistemas dinâmicos. Este campo de estudos tem como
origem os trabalhos em topologia de Marston Morse no início do século vinte [9], que o descreveu
como “estudo algébrico e geométrico da recorrência e transitividade". A idéia é dividir a superfí-
cie associada a um sistema dinâmico em um número finito de regiões e associa-las a símbolos. A
seqüência de símbolos gerados pela passagem de uma trajetória do sistema dinâmico (associada a
um ponto inicial) pelas regiões correspondentes, gera um sistema dinâmico “simbólico", que reflete
comportamentos quantitativos e qualitativos do sistema original, como por exemplo o tempo médio
em que o sistema permanece em uma região, ou se uma região torna-se periódica.
A teoria de dinâmica simbólica teve seu escopo de aplicações expandido ao ser usada como
ferramenta matemática nas teorias de código e informação, a partir do emprego de ferramentas para
análise de propriedades entre conjuntos de seqüências infinitas e dos mapeamentosentre estes. Como
por exemplo, a teoria de dinâmica simbólica tem sido usada no estudo de codificadores de linha e
decodificadores de janela deslizante [10], [11].
Autômatos
Com as tentativas de esclarecer questões sobre a natureza das demonstrações matemáticas, foi
estabelecida a definição de algoritmo. Como meio de avaliar os algoritmos, dois métodos de classifi-
cação foram desenvolvidos. O primeiro os classifica pelo tempo de execução, sendo conhecido como
teoria da complexidade. O segundo os classifica de acordo com a quantidade de memória necessária
para implementação, sendo conhecido como teoria da linguagem. De acordo com esta última, os al-
goritmos mais simples são aqueles que podem ser implementados por autômatos finitos, sendo estes
objetos de nosso interesse.
A teoria de autômatos, tema largamente explorado na teoria de linguagens formais, é utilizada no
estudo de seqüências de símbolos gerados por uma máquina de estados finitos. Devido ao repertório
de algoritmos originados na teoria de autômatos e com aplicação em teoria de grafos, avanços na
teoria de dinâmica simbólica têm sido obtidos pela aplicação de resultados da teoria de autômatos.
Como exemplo, a teoria de autômatos tem sido usada na simplificação de conjuntos finitos de se-
17
qüências e de grafos usados para representar sistemas simbólicos.
1.3 Objetivos da Dissertação
Como objetivos deste trabalho, inicialmente, construiremos algoritmos de complexidade linear
que gerem o grafo determinístico com o menor número de vértices (dadas certas restrições) e que
representem a classe dos sistemas dinâmicos simbólicos de memória finita ou SFT (do inglês shift of
finite type). Posteriormente, estenderemoso método apresentadopara sistemas dinâmicos simbólicos
de memória finita periódicosou PFT (do inglês periodicshift of finite type). Para este caso, iremos nos
concentrar nos sistemas dinâmicos simbólicos PFT irredutíveis, por serem estes de maior interesse
prático.
1.4 Organização da Dissertação
Esta dissertação estáorganizada em quatro capítulos. O Capítulo 2 introduz conceitose definições
da teoria de autômatos e dinâmica simbólica. O Capítulo 3 apresenta um novo algoritmo para gerar o
grafo determinístico com o menor número de vértices que apresenta um sistema dinâmico simbólico
de memória finita. No Capítulo 4 estendemos o algoritmo do Capítulo 3 para o caso de sistemas
dinâmicos simbólicos de memória finita periódicos.
18
CAPÍTULO 2
AUTÔMATO, DINÂMICA SIMBÓLICA E
GRAFO: CONCEITOS E RELAÇÕES
As relações entre a teoria de autômatos, multi-grafos direcionados e dinâmica simbólica têm sido
usadas por vários autores para obtenção de novos resultados e novas aplicações para estas teorias
[12],[13], [14]. Neste trabalho também usamos estas relações para obtenção de novos resultados.
Neste capítulo, apresentaremos os conceitos básicos de cada teoria, definiremos a nomenclatura
usada nesta dissertação e destacaremos algumas relações conhecidas entre estas teorias. Para uma
abordagem mais detalhada sobre dinâmica simbólica e teoria de grafo, o livro de Douglas Lind e
Brian Marcus [10] é o material mais indicado. Para uma abordagem introdutória nestas áreas com
extensa revisão bibliográfica e que explora as correlações com a teoria de autômatos, indicamos o
tutorial de Marie-Pierre Béal e Dominique Perrin [12]. Para a teoria de autômatos sugerimos [15],
[16] e [17], com ênfase para o último.
2.1 Teoria de Autômatos: alfabeto, palavras e linguagem
Informação é usualmente representada como uma seqüência de símbolos obtidos de um con-
junto arbitrário. Chamaremos de
alfabeto
qualquer conjunto de símbolos usado com esta conotação,
representando-o por A. Os elementos de A são chamados de
letras
ou
símbolos
. Para n ≥ 0 um
inteiro, a lista de símbolos (a
1
, a
2
, . . . , a
n
), a
i
∈ A, é chamada de
palavra
ou
seqüência
de compri-
mento n, sendo representada por a
1
a
2
. . . a
n
. A palavra de comprimento zero ( ), n = 0, é chamada
de palavra nula e representada por ε. Se para uma seqüência b
1
. . . b
m
de símbolos em A verifica-se
que b
1
. . . b
m
= a
i
. . . a
j
, 1 ≤ i ≤ j ≤ n, então b
1
. . . b
m
é uma
sub-palavra
de a
1
. . . a
n
. Repre-
sentamos por |w| o comprimento de uma palavra w em A. Assim, para {a, b, c} ∈ A e w = aabcb
temos que |w| = 5. Particularmente, |ε| = 0.
Dado duas palavras u e v com símbolos em um alfabeto A, podemos formar uma nova palavra
u · v, chamada a concatenação de u e v, pela justaposição dos símbolos de u com os símbolos de v.
Exemplificando, se u = a
1
a
2
. . . a
n
e v = b
1
b
2
. . . b
m
, então u · v = a
1
a
2
. . . a
n
b
1
b
2
. . . b
m
, ou seja,
a concatenaçãogerou uma nova palavra com símbolos emA ondeos n primeiros símbolos coincidem
com u e os m últimos símbolos coincidem com v. Usualmente, denotaremos a concatenação de u e
v por uv, em substituição a u · v. Decorre da operação de concatenar palavras que |uv| = |u| + |v|,
assim |uε| = |u|+|ε| = |u|. Concluímos que ε é o elemento identidadeda operaçãode concatenação,
ou seja, uε = εu = u.
Se A e B são conjuntos de palavras com símbolos em A, denota-se pela concatenação de A e B
o conjunto AB = {uv|u ∈ A e v ∈ B}. Decorre da operação de concatenação entre conjuntos que
A
+
=
∞
i=1
A
i
, onde A
1
= A e para n ≥ 2, A
n
= A
n−1
A. O conjunto A
∗
= ε ∪ A
+
recebe
a denominação especial de
fechamento de Kleene
, denominação justificada na teoria algébrica da
linguagem, sendo o sobrescrito “ ∗ ” denominado
estrela de Kleene
. Qualquer subconjunto de A
∗
é denominado uma
linguagem formal
(por simplicidade, iremos chamá-lo de linguagem). Assim,
A ⊆ A
∗
é uma linguagem. O complemento de B com relação a A é definido como B
′
= {v| v ∈
A e v /∈ B}. O conjunto de prefixos de A, representado por P(A), é definido como P(A) =
{v| ∃ u ∈ A
∗
, vu ∈ A}, e o conjunto de sufixos de A, representado por S(A), é definido como
S(A) = {v| ∃ u ∈ A
∗
, uv ∈ A}. Para A = {110}, segue o cálculo de P(A) e S(A).
P({110}) = { ε, 1, 1 1, 110} e S({110} ) = {ε, 0, 10, 110}
Definimos os conjuntos AB
−1
= {v| ∃ u ∈ B, vu ∈ A} e B
−1
A = {v| ∃ u ∈ B, uv ∈ A}, como
exemplos:
{111, 110, 000}{1}
−1
= {11} e {1}
−1
{111, 110, 000} = {11, 10}
2.2 Dinâmica Simbólica
Apresentamos nesta seção uma introdução aos conceitos de Dinâmica Simbólica [10]. Primeira-
mente, denotamos por A
Z
o conjunto de todas as seqüências bi-infinitas de símbolos em um alfabeto
20
A e chamamos estas seqüências de
pontos
em A
Z
. Assim, um ponto em A
Z
é uma seqüência
x = (x
i
)
i∈Z
= . . . x
−1
x
0
x
1
. . .
onde x
i
∈ A é a i-ésima
coordenada
de x. Definimos a
função deslocamento
como σ : A
Z
→ A
Z
,
tal que, (σ(x))
i
= x
i+1
para qualquer i ∈ Z. A função σ é inversível e {σ
n
| n ∈ Z} constitui uma
ação do grupo infinito (Z, +) sobre o conjunto A
Z
.
O conjunto A
Z
pode ser interpretado como um espaço topológico. Considerando a métrica dis-
creta associada ao conjunto A,
ρ(α, β) =
0 se α = β,
1 se α = β.
define-se a métrica do espaçodiscreto associado a i-ésima coordenadado espaço de dimensãoinfinita
A
Z
:
ρ
i
(α, β) =
ρ(α, β)
2
|i|−1
.
A métrica do espaço produto A
Z
formado pelos espaços discretos associados as suas coordenadas é
dada por:
d(x, y) = max
−∞<i<∞
{ρ
i
(x
i
, y
i
)}.
Portanto, a métrica associada pode ser definida por d(x, y) = 2
−e(x,y)
, onde e(x, y) = max{n ≥
0| x
i
= y
i
, −n ≤ i ≤ n} e por convenção, e(x, y) = ∞ se x = y e e(x, y) = −1 se x
0
= y
0
.
Lembramos que para qualquer x ∈ A
Z
e r > 0, a
bola aberta
de raio r em torno de x é o conjunto
B
r
(x) = {y ∈ A
Z
| d(x, y) < r}. Um subconjunto X ⊆ A
Z
é
aberto
, se para todo x ∈ X há
um r > 0, tal que B
r
(x) ⊆ X. Um subconjunto Y ⊆ A
Z
é fechado se seu complemento A
Z
\Y é
aberto.
Um
sistema dinâmico simbólico fechado
ou simplesmente
sistema simbólico fechado
, ou ainda
espaço invariante por deslocamento
(do inglês shift space) é um subconjunto X de A
Z
, tal que:
⊲ X é fechado;
⊲ X é invariante por deslocamento, i.e. σ(X) = X.
Equivalentemente, um sistema simbólico fechado X tem como propriedade característica que
para qualquer x ∈ A
Z
, se toda sub-palavra de x pertence a algum ponto de X, então x pertence a
X. Assim, um sistema simbólico fechado é completamente caracterizado pela coleção de palavras
21
presentes em seus pontos, podendo ser representadopor X ou (X, σ) para enfatizar o papelda função
deslocamento σ.
Lembramos que um espaço métrico M é
compacto
se, e somente se, todo seqüência em M
possui uma subseqüênciaconvergente [18, Teorema 43.5]. Como A
Z
é compacto e X é fechado [10,
Exemplo 6.1.17], X também é compacto [18, Teorema 43.8] (entre outras propriedades herdadas de
A
Z
), o que aumenta o interesse nestes como objeto de estudo em dinâmica simbólica.
Exemplo 2.1. Seja A = {0, 1} e S = {x ∈ A
Z
| ∃ n ∈ Z, x
i
= 0 para i ≤ n e x
i
= 1 para i >
n} um sistema simbólico, pela definição de S, este é invariante por deslocamento, contudo, não
é fechado. Para verificarmos esta afirmação, observemos que a seqüência formada só por zeros
y = . . . 000 . . . pertence a A
Z
\S, no entanto, para qualquer 0 < r ≤ 1 ou r = 2 (contradomínio
da função d(x, y), onde x, y ∈ A
Z
) existe uma seqüência bi-infinita x = (x
i
)
i∈Z
, x
i
= 0 para
i ≤ ⌈−log
2
r + 1⌉ e x
i
= 1 para i > ⌈−log
2
r + 1⌉, tal que, x ∈ B
r
(y) e x /∈ A
Z
\S, ou seja,
B
r
(y) A
Z
\S. Portanto, o complemento de S com relação ao conjunto A
Z
não é aberto, logo, S
não é um sistema simbólico fechado. A existência de um seqüência em A
Z
que não pertence a S,
mas com todos os seus fatores sendo fatores de seqüências de S, implica que S não é fechado.
No contexto de dinâmica simbólica, uma palavra sobre um alfabeto A também é chamada de
bloco
, sendo ε chamado de bloco vazio. Utilizamos A
k
para nos referirmos ao conjunto de todos os
blocos de comprimento k em A. Se w ∈ A
k
, w é chamado de um k-bloco. Um
fator
ou
sub-bloco
de um bloco u = a
1
a
2
. . . a
k
é um bloco a
i
a
i+1
. . . a
j
, onde 1 ≤ i ≤ j ≤ k. Por convenção, ε
é um fator de todo bloco. Para todo x ∈ A
Z
e i ≤ j, denota-se o bloco em x, da coordenada i
a j por x
[i,j]
= x
i
x
i+1
. . . x
j
. Se i > j, define-se x
[i,j]
= ε. Como simples extensão, define-se
x
[i,j)
= x
i
x
i+1
. . . x
j−1
e assim, x
[i,∞)
= x
i
x
i+1
. . . é denominada seqüência infinita à direita e
x
(∞,i]
= . . . x
i−1
x
i
seqüência infinita à esquerda, ressaltando que as duas últimas não são blocos, já
que não possuem comprimento finito.
Como conseqüência das propriedades de um sistema simbólico fechado X ⊆ A
Z
, podemos
determiná-lo a partir de um subconjunto de A
∗
. Inicialmente, vamos definir o
conjunto cilindro
,
C
X
k
(u), como sendoo conjunto dospontos x ∈ X para os quaisu é um fator iniciando na coordenada
k, i.e., C
X
k
(u) = {x ∈ X | u = x
[k,k+|u|−1]
}. Como X é um conjunto fechado, então podemos
afirmar que A
Z
\X é aberto. Assim, para todo y ∈ A
Z
\X existe k = k(y), tal que para u
y
= y
[−k,k]
,
então C
A
Z
−k
(u
y
) ⊆ A
Z
\X. O conjunto F = {u
y
| y ∈ A
Z
\X} é suficiente para definir X. Para
verificarmos esta afirmação, suponha que para u
y
∈ F existe x ∈ X tal que u
y
= x
[i,j]
, então
σ
(i+k)
(x) ∈ C
A
Z
−k
(u
y
), o que é uma contradição já que X é invariante por deslocamento.
22
Dado um subconjunto F ⊆ A
∗
, se X é o conjunto de pontos em A
Z
que não possuem fatores
em F, então A
Z
\X é aberto, consequentemente X é fechado. Para qualquer x ∈ X temos que
σ(x) ∈ X (se x não possui fatores em F, σ(x) também não possui). Concluímos que X é um
subconjunto de A
Z
fechado e invariante por deslocamento, ou seja, um sistema simbólico fechado.
Isto nos permite definir um sistema simbólico fechado, X, a partir de um conjunto F ⊆ A
∗
como: X
é o conjunto de pontos em A
Z
que não possuem blocos em F. A relação entre X e F é representada
pela equação X = X
F
, onde a notação X diz respeito à operação de formar o conjunto X e este
é o conjunto resultante da operação. Da propriedade associada ao conjunto F, este é chamado de
conjunto proibido
.
Exemplo 2.2. Seja A = {e, f, g} e X o conjunto de seqüências de A
Z
para as quais o e só pode ser
seguido por e ou f, f por g, g por e ou f. Assim, F = {eg, ff, fe, gg}.
Exemplo 2.3. Seja X ⊂ A
Z
, A = {a, b, c}, tal que, as palavras da forma ab
m
c
k
a ocorrem em
seqüências de X se, e somente se, m = k. X é conhecido como o sistema simbólico fechado livre
de contexto e possui conjunto proibido F = {ab
m
c
k
a |m = k, m, k ≥ 0}.
A definição do conjunto F realça a observação feita acima sobre a determinação de um sistema
simbólico fechado X pelo conjunto de todos os fatores em pontos de X. Em alguns casos é mais
fácil especificar X por este conjunto que por F, o que justifica a próxima definição. Seja X um
sistema simbólico fechado e B
n
(X) o conjunto de todos os n-blocos que ocorrem em pontos de X.
A
linguagem
de X é a coleção
B(X) =
∞
n=0
B
n
(X).
Apesar de todo conjunto proibido F ⊆ A
∗
determinar um sistema simbólico fechado em A,
nem toda linguagem em A
∗
determina um sistema simbólico fechado. Um subconjunto em A
∗
deve
satisfazer as propriedades listadas na Propriedade 2.1 para ser a linguagem de um sistema simbólico
fechado [10, Proposição 1.3.4].
Propriedade 2.1.
(a) Seja X um sistema simbólico fechado e B(X) sua linguagem. Se w ∈ B(X), então:
⊲ Todo sub-bloco de w pertence a B(X) , portanto B(X) é uma
linguagem fatorial
;
⊲ Há blocos não vazios u e v em B(X) tal que uwv ∈ B(X), portanto B(X) é uma
linguagem
prolongável
.
23
(b) A linguagem de um sistema simbólico fechado é caracterizada por (a), ou seja, se L ⊆ A
∗
, então
L é a linguagem de algum sistema simbólico fechado X se, e somente se, L satisfaz a condição
(a).
(c) A linguagem de um sistema simbólico fechado X o caracteriza, pois X = X
B(X)
′
. Assim, dois
sistemas simbólicos fechados são iguais se, e somente se, eles têm a mesma linguagem.
Na prática os sistemas simbólicos fechados de maior interesse são os
irredutíveis
, sendo aqueles
que para quaisquer u, v ∈ B(X), existe um w, tal que, uwv ∈ B(X). Neste caso B(X) é dita uma
linguagem transitiva
(formalmente, uma linguagem formal L ⊆ A
∗
é transitiva se ∀u, v ∈ L, ∃w ∈
A
∗
tal que uwv ∈ L). Quando B(X) não é transitiva dizemos que X é um sistema simbólico
fechado
redutível
.
Exemplo 2.4. Seja S um subconjunto dos inteiros não negativos. Se S é finito, define-se X = X(S)
como o conjunto de todas as seqüências binárias bi-infinitas para as quais o 1 ocorre infinitas vezes
em cada direção e, tal que, o número de ocorrências do 0 entre uns consecutivos é um inteiro em S.
Assim, x = . . . 10
n
−1
10
n
0
10
n
1
1 . . . , onde n
i
∈ S, é uma seqüência típica do conjunto X(S). Caso
consideremos o conjunto S infinito, então 0
n
∈ B(X(S) ) para todo n ≥ 0, no entanto, a seqüência
y = . . . 000 . . ., composta só por zeros, não pertence a X(S). Portanto, X(S) não é um sistema
simbólico fechado se S é infinito. Seja S finito e m = max{n |n ∈ S}, um possível conjunto
pribido para X(S) é F = {10
n
1 | n ≥ 0 e n /∈ S} ∪ {0
m+1
}.
Um importante conceito em dinâmica simbólica é o de
sistema dinâmico
, representado por
(M, φ), onde M é um espaço métrico compacto e φ : M → M é uma função contínua. Se φ é
um
homeomorfismo
(φ é contínua, injetiva, sobrejetiva e seu inverso é contínuo), (M, φ) é chamado
um sistema dinâmico inversível. Um homeomorfismo importante, já apresentado neste texto, é a
função σ, sendo (X, σ
X
) (o subscrito indica a restrição de σ ao subconjunto X de A
Z
) interpretado
como o mapeamento subjacente que provê a dinâmica, tal que, se (X, φ) é um sistema dinâmico,
então σ
X
◦ φ = φ ◦ σ
X
, ou seja, o comportamento do sistema dinâmico é invariante no “tempo".
Com o conceito de sistema dinâmico surge a questão: Como dois sistemas dinâmicos estão rela-
cionados? Para abordá-la, partimos da definição de um
homomorfismo
θ : (M, φ) → (N, ψ) entre
sistemas dinâmicos como sendo a função contínua θ : M → N satisfazendo a propriedade comuta-
tiva ψ ◦ θ = θ ◦ φ, representada pelo diagrama
24
M
φ
−−−−→ M
θ
θ
N −−−−→
ψ
N
Se θ é injetiva e sobrejetiva, como M é compacto, então o mapeamento inverso θ
−1
também
é contínuo. Neste caso, θ é chamado de
conjugado topológico
e é escrito como θ : (M, ψ)
∼
=
(N, φ). Quando há um conjugado topológico entre dois sistemas dinâmicos, estes são chamados de
topologicamente conjugados
.
Consideremos o importante caso quando ψ e φ são funções deslocamento. Dado os sistemas
dinâmicos fechados (X, σ
X
) e (Y, σ
Y
) sobre A
Z
e B
Z
, respectivamente,seja θ : (X, σ
X
) → (Y, σ
Y
)
um homomorfismo. Como A
Z
é compacto e X fechado, então θ é uniformemente contínua. Con-
sequentemente, há um inteiro k tal que para todo ponto x ∈ X, (θ(x))
0
é determinado pelo bloco
x
[−k,k]
. Como θ comuta com a função deslocamento, então qualquer símbolo de θ( x) é determinado
por um bloco de comprimento (2k + 1).
A importância deste resultado reside na determinação parcial da relação entre homomorfismos
e
códigos de bloco deslizante
(SBC, do inglês sliding block codes). Um SBC mapeia seqüências
. . . x
−1
x
0
x
1
. . . de um sistema dinâmico fechado X sobre A em seqüências . . . y
−1
y
0
y
1
. . . sobre
um alfabeto B. Uma apresentação mais precisa requer a especificação de um mapeamento de bloco,
que é uma função Φ : B
m+n+1
(X) → B, ou seja, de blocos em B
m+n+1
(X) para símbolos de um
alfabeto B. Assim, a função φ : X → B
Z
definida por y = φ(x), onde y
i
= Φ(x
i−m
. . . x
i+n
) =
Φ(x
[i−m,i+n]
), é um SBC de
memória
m e
antecipação
n induzido por Φ, o que é representado por
φ = Φ
[−m,n]
∞
, ou simplesmente φ = Φ
∞
, se a memória e antecipação são conhecidos. Quando
Y ⊆ B
Z
é um sistema simbólico fechado e φ(X) ⊆ Y , então escrevemos φ : X → Y .
Seja φ : X → Y um SBC entre os sistemas simbólicos fechados X e Y . Sejam x, x
′
∈ X tal
que e(x, x
′
) ≥ m + n + 1, então e(φ(x), φ(x
′
)) ≥ e(x, x
′
) − (m + n), logo dada uma seqüência
de pontos em X, {x
n
}
∞
n=1
, se lim
n→∞
d(x, x
n
) = 0 (isto é, se {x
n
}
∞
n=1
converge para x) então
lim
n→∞
d(φ(x), φ(x
n
)) = lim
n→∞
d(x, x
n
) · 2
m+n
= 0. Assim, um SBC é uma função contínua.
Seja y = φ(x), observemos que φ(σ
X
(x))
i
= Φ(x
[i+1−m,i+1+n]
) = y
i+1
= σ
Y
(φ(x))
i
, portanto
φ ◦ σ
X
= σ
Y
◦ φ, logo um SBC comuta com a função deslocamento. Concluímos que uma função
θ : (X, σ
X
) → (Y, σ
Y
), onde (X, σ
X
) e (Y, σ
Y
) são sistemas simbólicos fechados, é um SBC se, e
somente se, θ é um homomorfismo.
25
2.3 Autômato: Linguagem Regular
Um autômato finito é definido pela quíntupla A = (V, E, λ, I, T ), onde: V é um conjunto finito
de
vértices
(ou
estados
); E é um conjunto finito de
ramos
, ao qual definem-se as funções i : E → V
e t : E → V, que determinam o estado inicial e o terminal de um ramo, respectivamente; λ : E → A
é a
função de rotulação
; I ⊆ V é o conjunto de
estados iniciais
; por fim, T ⊆ V é o conjunto de
estados terminais
. Temos particular interesse em autômatos determinísticos, isto é, para quaisquer
e
1
, e
2
∈ E, se i(e
1
) = i(e
2
) e λ(e
1
) = λ(e
2
) então e
1
= e
2
. A Figura 2.1 mostra um autômato finito,
onde V = {I, J, K}, I = {I} (indicado pela seta apontando para o círculo associado ao vértice),
T = {K} (indicado pelo círculo interno associado ao vértice).
I K
J
e
2
e
1
e
3
e
4
Figura 2.1: Autômato finito.
Quando o autômato é determinístico, também é comum defini-lo pela quíntupla A = (V, A,
δ, I, T ), onde A é o alfabeto e δ : B → V, B ⊆ V × A, é a
função de transição
, que determina os
ramos e seus rótulos, e.g.,seja δ(I, a) = J temos I como estado inicial, J como estado finale a como
rótulo. Estas representações de um autômato são equivalentes, podendo-se gerar uma representação
a partir da outra. Assim, para todo (I, a) ∈ B incluímos e em E, tal que i(e) = I, t(e) = δ(I, a) e
λ(e) = a. Ao contrário, para todo e ∈ E incluímos (i(e), λ(e)) em B e definimos δ(I, a) = t(e). Um
autômato A
′
= (V
′
, E
′
, λ
′
, I
′
, T
′
) é um sub-autômato de A = (V, E, λ, I, T ), se V
′
⊆ V, I
′
⊆ I,
T
′
⊆ T , todo e ∈ E para o qual i(e), t(e) ∈ V
′
pertence a E
′
e λ
′
= λ|E
′
.
Uma seqüência π = e
1
. . . e
n
∈ E
∗
é um
caminho
em um autômato A se t(e
i
) = i(e
i+1
), 1 ≤
i < n. Seja P (A) = {π| π é um caminho em A}, podemosestendera função rotulação λ : P (A) →
A
∗
, tal que, se π = e
1
. . . e
n
então λ(π) = λ(e
1
) . . . λ(e
n
). As funções i e t também podem
ser estendidas para i, t : P (A) → V, tal que i(π) = i(e
1
) e t(π) = t(e
n
). Agora dispomos
de ferramentas suficientes para introduzirmos o conceito de uma linguagem apresentada por um
autômato. Seja L ⊆ A
∗
, L é apresentada por um autômato A se L = {λ(π)| π ∈ P (A), i(π) ∈
I e t(π) ∈ T }. Denota-se por L(A) a linguagem apresentada por um autômato A.
26
Uma questão natural neste ponto é: dada uma linguagem L, quando há um autômato finito A
tal que L = L(A)? A resposta foi dada por Kleene, sendo um dos teoremas fundamentais da teoria
da computação. Para expormos a idéia envolvida, considere C uma coleção de linguagens formais
sobre um alfabeto A. A coleção C é dita fechada sob união (+), concatenação (·) e fechamento de
Kleene (∗), chamados de
operadores regulares
, se dadasduas linguagensquaisquerL e M em C então
L + M , L ·M, L
∗
e M
∗
também estão em C. Seja
¯
C o fechamento de C sob os operadores regulares,
conhecido como
fechamento regular
de C e descrito como: se C
(n)
são todas as linguagens obtidas
de C por n aplicações dos operadores regulares, então
¯
C =
∞
i=0
C
(n)
, onde C
(0)
= C. Observe que,
há uma equação em
¯
C com n ocorrências de operadores regulares para qualquer n ≥ 0, mas que
dada uma equação em
¯
C há um número finito de operadores regulares. A importância do conjunto
¯
C
decorre da seguinte propriedade.
Propriedade 2.2.
(1) Linguagens finitas são apresentadas por autômatos [17, Proposição 2.2.4].
(2) Se L é a união de duas linguagens apresentadas por autômatos, então L é apresentada por um
autômato [17, Proposição 2.5.6].
(3) Se L é a concatenação de duas linguagens apresentadas por autômatos, então L é apresentada
por um autômato [17, Proposição 3.3.4].
(4) Se L é apresentada por um autômato, então L
∗
também é apresentada por um autômato [17,
Proposição 3.3.6].
Dado um alfabeto A, estamos interessados nos casos em que C = {ε} ∪ {∅} ∪ A. Como {ε},
{∅} e A são apresentadas por autômatos, conforme ilustram as Figuras 2.2-2.4, concluímos da Pro-
priedade 2.2 que as linguagens no fechamento regular
¯
C de C, chamadas de
linguagens regulares
,
são apresentadas por autômatos (a prova deste resultado é realizada por indução do número de ope-
radores regulares, partindo-se do conjunto ∅∪{ε}∪A [17, Teorema 5.2.1]). Como os elementos em
¯
C são formados por expressões (compostas por um número finito de elementos em C e operadores
regulares), estes também são chamados de
expressões regulares
, ou seja, uma expressão regular é
uma forma de representar uma linguagem regular e a toda linguagem regular está associada uma
Figura 2.2: Linguagem ∅. Figura 2.3: Linguagem {ε}.
a
Figura 2.4: Linguagem {a}.
27
expressão regular.
Os autômatos nas Figuras 2.2-2.4 possuem no máximo um ramo e todos possuem expressões
regulares associadas. Este é o ponto de partida para uma prova por indução (no número de ramos
de um autômato finito) que a todo autômato finito está associado uma expressão regular, ou seja,
dado um autômato A, L(A) é uma linguagem regular. A prova algébrica que uma linguagem é
apresentada por um autômato se, e somente se, esta é regular é apresentada em [17, Teorema 5.2.1].
Uma provaconstrutiva, baseadaem algoritmos que geram um autômato dadauma expressãoregular e
uma expressão regular dado um autômato, é apresentada em [17, Seção 5.3]. Esse problema também
é abordado em [16, Capítulo 2].
Em alguns algoritmos o contra domínio da função de rotulação é estendido λ : E → A ∪ {ε}.
Quando no autômato há ramos com rótulo ε, este é dito com transição ε. Esta modificação não impõe
restrições teóricas e algorítmicas, já que dado um autômato com transições ε é possível transformá-
lo em um autômato não determinístico, bem como transformar este último em um determinístico.
Em suma, os diferentes tipos de autômatos empregados para apresentar uma linguagem regular são
equivalentes. Os autômatos determinísticos desempenham um papel importante no estudo de lin-
guagens regulares, a saber, na teoria algébrica de linguagens é um autômato determinístico que está
relacionado com o monóide sintático associado à linguagem. O algoritmo accessible subset con-
struction utilizado para gerar autômatos determinísticos a partir de autômatos não determinísticos é
apresentado em [17, Algoritmo 3.2.5] e [15, Capítulo 2].
Dado um vértice I para o qual não há caminhos originados em I que o alcançam, ou do qual
não há caminhos para vértices em T ; este pode ser removido juntamente com os ramos e ∈ E,
t(e) = I ou i(e) = I. Um autômato que não permite tal eliminação de vértices é dito
essencial
.
Como estamos interessadosem autômatos determinísticos e com o menornúmero de vértices, sempre
iremos considerá-los essenciais.
Mínima apresentação determinística
Dado A = (V, E, λ, I, T ) um autômato sem transições ε, seja I ∈ V. O contexto à direita e à
esquerda de I em A são, respectivamente, os conjuntos:
F
A
(I) = {λ(π)| π ∈ P (A), i(π) = I e t(π) ∈ T },
B
A
(I) = {λ(π)| π ∈ P (A), i(π) ∈ I e t(π) = I}.
28
Há conceitos similares para uma dada linguagem L e as palavras w ∈ A
∗
. O contexto à direita e à
esquerda de w ∈ A
∗
com respeito a L são, respectivamente, os conjuntos:
F
L
(w) = {u| u ∈ A
∗
e wu ∈ L},
B
L
(w) = {u| u ∈ A
∗
e uw ∈ L}.
Os conjuntos F
A
e F
L
são definidos para conjuntos de elementos distintos, enquanto F
A
é
definido para o conjunto de vértices do autômato A, F
L
é definido para as palavras em A
∗
. Assim,
podemos escrever F
A
(I) como F(I) e F
L
(w) como F(w), pois que os argumentos I e w deixam
claro que estamos nos referindo a F
A
e F
L
, respectivamente.
Dado A = (V, E, λ, I, T ) obtemos A
∼
= (V/
∼
, E
∼
, λ
∼
, I
∼
, T
∼
) pela aplicação da relação de
equivalência ∼ sobre o conjunto V de A, a saber: I ∼ J se, e somente se, F(I) = F(J); sendo esta
relação chamada de redução sobre A. Os elementos de V/
∼
são as classes de equivalência obtidas
pela aplicação de ∼ sobre V e formam o conjunto de vértices de A
∼
. Dado I ∈ V é comum denotar-
se a classe de equivalência (ou vértice associado em V
∼
) a qual I pertence por [I]. Dito isto, há um
ramo e
∼
∈ E
∼
de [I] para [J] com rótulo a se, e somente se, há um ramo e ∈ E com i(e) ∈ [I],
t(e) ∈ [J] e λ(e) = a. Um vértice [I] será inicial se, e somente se, existe K ∈ [I] tal que K ∈ I.
Similarmente, [J] ∈ T
∼
se, e somente se, existe K ∈ [J], K ∈ T .
Um autômato é dito
reduzido
se as classes de equivalência de ∼ possuem um único elemento,
assim A
∼
é reduzido. Pelo processo de construção de A
∼
, este tem um número menor ou igual
de estados que A. Como L(A
∼
) = L( A) [17],[16], dado a apresentação A de uma linguagem L,
podemos obter uma outra com menor número de vértices pela construção de A
∼
. A importância de
se obter um autômato com menor número de vértices apresentando a mesma linguagem deve-se, por
exemplo, a sua aplicação em algoritmos cuja complexidade cresce com seu número de vértices.
Pode-se mostrar que sendo A determinístico então A
∼
é determinístico, portanto um autômato
reduzido e determinístico pode ser obtido aplicando-se um algoritmo de determinização seguido por
um de redução. Se um autômato finito reduzido e determinístico A tem um único estado inicial,
então este é dito
o mínimo autômato determinístico
que apresenta L(A), ou seja, é a apresentação
determinística com menor número de vértices da linguagem L(A). Para uma abordagem mais com-
pleta sobre redução de autômatos determinísticos, sugerimos [17, Capítulo 7] e [16, Seção 3.4]. Uma
abordagem algébrica é apresentada em [15, Capítulo 3]. Estes algoritmos possuem complexidade as-
sintótica n
2
, onden é o número de vértices. Para um algoritmo de complexidadeassintótica(n·log n)
consultar [19].
29
2.3.1 Grafos
Um grafo (formalmente, um multi-grafo direcionado) pode ser interpretado como um autômato
onde V = I = T . Devido a redundância na especificação dos conjuntos I e T , passamos a
representá-lo como G = (V, E, λ) (a troca do A pelo G é indicativo desta peculiaridade). Não
havendo ambigüidade com relação aos conjuntos V, E e a função λ, especificaremos o grafo por G.
Nosso interesse em grafos decorre da possibilidade de podermos apresentar alguns sistemas
dinâmicos por meio destes. Inicialmente, se considerarmos A = E, então um caminho bi-infinito
em G pode ser interpretado como um ponto em E
Z
, sendo X
G
o conjunto destes pontos (conhecido
na literatura como edge shift). Como todos os vértices do grafo são iniciais e terminais, a coordenada
0 de um ponto é estabelecida arbitrariamente, o que implica em σ(X
G
) = X
G
. Se x ∈ E
Z
possui to-
dos os seus fatores em P (G), então existe um caminho bi-infinito em G que apresenta x, ou seja, um
ponto não pertence a X
G
se, e somente se, tiver algum fator em E
∗
\P (G). Isto implica que E
Z
\X
G
é
aberto, assim X
G
é fechado. Concluímos que o sistema simbólico gerado pelos caminhos bi-infinitos
em um grafo é fechado. Pode-se mostrar que B(X
G
) = P (G).
Considerando G como uma forma de representar um sistema simbólico fechado, não há sen-
tido mantermos vértices que não sejam visitados por um caminho bi-infinito em G. Assim, pela
eliminação sucessiva de estados que não são terminais ou iniciais de algum ramo em E, obtemos a
componenteessencial do grafo G. Tal procedimento é finito já que V é um conjunto finito. A compo-
nente essencial obtida por este processo é única, se a designarmos por H temos que X
G
= X
H
[10,
Proposição 2.2.10]
Voltando ao caso de uma função λ : E → A arbitrária. A função Φ = λ induz um SBC
φ : X
G
→ A
Z
com memória e antecipação iguais a zero. A imagem de um sistema simbólico
fechado sob um SBC é um sistema simbólico fechado [10, Teorema 1.5.13], portanto, para um grafo
G, φ(X
G
) = λ
∞
(X
G
) é um sistema simbólico fechado. Por este motivo, chamaremos φ(X
G
) um
sistema simbólico regular, abreviado por SSR (conhecido na literatura como sofic shift). Note que
um SSR é fechado, apesar de não estar explicito na sigla.
Um grafo G é
irredutível
se para todo par ordenado de vértices (I, J) ∈ V × V há um caminho
π ∈ P (G), i(π) = I e t(π) = J. Assim, dado um SSR apresentado por um grafo G, onde λ(e) = e
(função identidade), se X
G
é irredutível então G é irredutível [10, Proposição 2.2.14]. Quando G não
é irredutível o chamamos de redutível, neste caso X
G
é redutível, mas o mesmo não pode ser dito de
λ
∞
(X
G
) para uma função λ arbitrária.
Exemplo 2.5. Seja X ⊂ A
Z
, A = {a, b}, tal que, entre ocorrências consecutivas de b o número
30
b
a
a
Figura 2.5: Apresentação do SSR par.
de ocorrências de a é par. X é chamado um sistema simbólico fechado par. O conjunto proibido
associado à X é F = ba(aa)
∗
b, portanto, a linguagem complementar à linguagem de X é A
∗
FA
∗
=
(a + b)
∗
ba(aa)
∗
b(a + b)
∗
. Como A
∗
FA
∗
é uma expressão regular, podemos representá-la por um
autômato e, assim, à sua linguagem complementar com relação a A
∗
, ou seja, a linguagem de X.
Portanto, X é um SSR. Um grafo representando X é apresentado na Figura 2.5.
Um grafo G é chamado
de sincronização
se para qualquer vértice I ∈ V pode ser associado um
bloco u ∈ B(X
G
), tal que qualquer caminho π ∈ P (G), λ(π) = u, tem-se que t(π) = I. A palavra
u é chamada uma
palavra de sincronização de
I
em
G, sendo dito que u
sincroniza
para I. Grafos
de sincronização desempenham um importante papel na determinação de apresentações com número
mínimo de vértices, o que ficará claro à frente.
Definição 2.1. Sejam G
i
= (V
i
, E
i
, λ
i
), i = 1, 2 , dois grafos essenciais. Um homomorfismo Φ de
G
1
para G
2
é definido pelo par de funções Φ
V
: V
1
→ V
2
e Φ
E
: E
1
→ E
2
, tal que
∀e
1
∈ E
1
, i(Φ
E
(e
1
)) = Φ
V
(i(e
1
)), t(Φ
E
(e
1
)) = Φ
V
(t(e
1
)) e λ
1
(e
1
) = λ
2
(Φ
E
(e
1
)).
Dizemos que Φ é um isomorfismo quando Φ
V
e Φ
E
são sobrejetivas e injetivas.
Observe que, para o caso determinístico, dados I = i(e
1
) e a = λ
1
(e
1
) podemos escrever
a primeira equação como i(Φ
E
(e
1
)) = Φ
V
(I), o que aplicado na segunda equação resulta em
t(Φ
E
(e
1
)) = δ(Φ
V
(I), a) e Φ
V
(t(e
1
)) = Φ
V
(δ(I, a)). Assim, o homomorfismo passa a ser definido
por uma única função Φ : V
1
→ V
2
satisfazendo δ(Φ(I), a) = Φ(δ(I, a)). Neste caso, Φ é um
isomorfismo quando é injetiva e sobrejetiva.
Mínima apresentação determinística de sincronização (m-SDP)
Alguns algoritmos que empregam grafos são tão mais complexos quanto maior a cardinalidade
do conjunto V, para alguns esta relação é exponencial. Isso justifica as recorrentes publicações de
algoritmos que se propõem a gerar apresentações com número mínimo de vértices. Uma questão que
antecedea proposiçãode tais algoritmos é: Dada uma apresentação,como saberse ela possuio menor
número de vértices possível? Esta questão vem sendo respondida por partes. Inclusive com restrições
31
de maior interesse às apresentações de um SSR. Particularmente, procura-se responder esta questão
para o caso de apresentações determinísticas. Aqui iremos abordá-la para o caso de apresentações
determinísticas de sincronização, para o qual as apresentações com menor número de vértices são
isomorfas, chamadas de
mínima apresentação determinística de sincronização
e abreviado por m-
SDP (do inglês minimal synchronizing deterministic presentation).
Seja G um grafo determinístico, essencial e não reduzido apresentando um SSR irredutível X =
λ
∞
(X
G
). Há um máximo sub-grafo irredutível em G que apresenta B(X) [13]. Para obtenção do
m-SDP, as classes de equivalência obtidas do conjunto de vértices deste sub-grafo são determinadas
(relação de equivalência dada por I ∼ J se, e somente se, F(I) = F(J)). Por fim, o grafo reduzido
é construído, no qual as classes de equivalência que foram determinadas são interpretadas como
os vértices desta apresentação. O grafo reduzido obtido é o Shannon cover ou m-SDP do SSR
irredutível, que é definido como uma apresentação reduzida, irredutível e determinística do SSR,
sendo isomorfas quaisquer apresentações que satisfaçam tais condições [10, Proposição 3.3.17].
Para o caso de uma apresentação redutível G, como podemos determinar se esta tem o menor
número de vértices? A resposta para esta questão foi dada em [13, Seção 5] para o caso de uma a-
presentação reduzida, determinística de sincronização. É demonstrado que qualquer tal apresentação
é isomorfa a um sub-autômato terminal do mínimo autômato que apresenta o SSR (um sub-autômato
A
′
= (V
′
, E
′
, λ
′
, I
′
, T
′
) de um autômato A = (V, E, λ, I, T ) é terminal se para I
′
∈ V
′
e e ∈ E,
i(e) = I
′
, então t(e) ∈ V
′
). Aquichegaremosao mesmo resultado mostrandoque duas apresentações
SDP e reduzidas de um SSR são isomorfas.
Definição 2.2. Seja L ∈ A
∗
uma linguagem. Uma palavra w ∈ A
∗
é uma
constante
para L se, e
somente se, para quaisquer u
1
, u
2
, u
3
, u
4
∈ A
∗
, u
1
wu
2
, u
3
wu
4
∈ L, então u
1
wu
4
∈ L. Usaremos
C(L) para denotar o conjunto de constantes para L que pertencem a L.
Lema 2.1. Seja G = (V, E, λ) um SDP reduzido de um SSR X = λ
∞
(X
G
). Uma palavra w é de
sincronização para I ∈ V se, e somente se, w ∈ C(B(X)).
Demonstração: Seja u
1
wu
2
∈ B(X), então existe τ πυ ∈ P (G) tal que λ(τπυ) = λ(τ)λ(π)
λ(υ) = u
1
wu
2
. Como w é de sincronização para I, i(υ) = t(π) = I. Assim, para qualquer
u
3
wu
4
∈ B(X), se λ(τ
′
π
′
υ
′
) = u
3
wu
4
então i(υ
′
) = t(π
′
) = I, onde τ
′
π
′
υ
′
∈ P (G). Isso implica
que τπυ
′
∈ P (G) e assim que λ(τπυ
′
) = u
1
wu
4
∈ B(X).
Sejam w ∈ C(B(X)) e π
1
, π
2
∈ P (G) tais que λ(π
1
) = λ(π
2
) = w, t(π
1
) = I
1
, i(π
1
) = J
1
,
t(π
2
) = I
2
e i(π
2
) = J
2
. Como G é de sincronização, existem palavras w
1
e w
2
de sincronização
para J
1
e J
2
, respectivamente. Assim, para todo v ∈ F(I
1
), w
1
wv, w
2
w ∈ B(X), w
2
wv ∈ B(X).
32
Isto implica que F(I
1
) ⊆ F(I
2
). Similarmente, F(I
2
) ⊆ F(I
1
). Concluímos que F(I
1
) = F(I
2
).
Como G é reduzido, temos que I
1
= I
2
.
Proposição 2.2. Se G = (V, E, λ) e G
′
= (V
′
, E
′
, λ
′
) são apresentaçõesSDP e reduzidas de um SSR
X, então estas são isomorfas.
Demonstração: Seja w ∈ C(B(X)) uma palavra de sincronização para I ∈ V. Definimos
Φ : V → V
′
, tal que Φ(I) = I
′
se há um caminho π
′
∈ P (G
′
) para o qual λ(π
′
) = w e t(π
′
) = I
′
.
Inicialmente demonstraremos que Φ é bem definida, para isso consideremos w, u ∈ C(B(X)). Do
Lema 2.1, w e u são de sincronização em G, considerando que w e u sincronizam para o mesmo
vértice I ∈ V, então F(w) = F(u). Como w e u também são palavras de sincronização em G
′
(novamente do Lema 2.1) então elas sincronizam para o mesmo vértice em V
′
. Ou seja, Φ é uma
função.
Agora provaremos que Φ é injetiva e sobrejetiva, respectivamente. Seja Φ(I
1
) = Φ(I
2
) = I
′
, en-
tão há palavras de sincronização w
1
, w
2
∈ C(B(X)) que sincronizam para I
1
e I
2
, respectivamente.
Assim, w
1
e w
2
sincronizam para I
′
em G
′
, isso implica que F(w
1
) = F(w
2
). Como G é reduzido,
concluímos que I
1
= I
2
. Seguindo com a demonstração que Φ é sobrejetiva, seja w uma palavra de
sincronização para I
′
∈ V
′
. Do Lema 2.1, w ∈ C(B(X)) e, assim, também é de sincronização em
G. Seja I ∈ V o vértice para o qual w sincroniza, então Φ(I) = I
′
.
Para provarmos que Φ é um homomorfismo, consideremos que a ∈ A e w sincroniza para I ∈ V.
Se Φ(δ(I, a)) = I
′
então wa sincroniza para I
′
. Como w sincroniza para a imagem de I em V
′
,
δ(Φ(I), a) = I
′
, ou seja, Φ(δ(I, a)) = δ(Φ(I), a). Concluímos que G é isomorfo a G
′
.
2.4 Sistemas Simbólicos Fechados de Memória Finita (SFT)
Um sistema simbólico fechado de memória finita X (do inglês shift of finite type, abreviado
por SFT) é um sistema simbólico fechado para o qual existe um conjunto proibido finito F, ou
seja X = X
F
para um F finito. Como propriedade característica de um SFT, sempre é possível
determinar um inteiro não negativo M, tal que para todo v ∈ B(X), |v| ≥ M , se uv, vw ∈ B(X)
então uvw ∈ B( X). O menor M para o qual esta propriedade pode ser verificada é chamado
a
memória
do SFT. Alguns autores definem a memória do SFT como o máximo comprimento de um
bloco em F. Estas denominações são idênticas quando o conjunto F é mínimo, o que será discutido
em capítulos posteriores. Como propriedade complementar de um SFT X, se φ : X → Y é um
33
SBC conjugado (o termo conjugado informa que φ é injetivo e sobrejetivo e, portanto, inversível [10,
Teoema 1.5.14]) então Y também é um SFT [10, Teorema 2.1.10].
Seja X ⊆ A
Z
um SSR apresentado por G = (V, E, λ). Dado qualquer bloco e
1
e
2
. . . e
n
∈ E
∗
,
então e
1
e
2
. . . e
n
∈ B(X
G
) se, e somente se, t(e
i
) = i(e
i+1
), 1 ≤ i < n. Ou seja, X
G
é um SFT
com M = 1. Isto implica que todo SSR é imagem de um SFT pela aplicação de um SBC sobrejetivo,
neste caso induzido por Φ : B
2
(X
G
) → A, onde Φ(e
1
e
2
) = λ(e
2
).
Adicionalmente, seja Y ⊆ A
Z
um SFT, podemos construir uma apresentação G para Y definida
por: G = (B
M
(Y ), B
M +1
(Y ), λ), tal que para todo a
1
a
2
. . . a
M +1
∈ E temos que λ(a
1
a
2
. . .
a
M +1
) = a
M +1
, i(a
1
a
2
. . . a
M +1
) = a
1
a
2
. . . a
M
e t(a
1
a
2
. . . a
M +1
) = a
2
. . . a
M +1
. Nes-
tas apresentações só há um ramo de a
1
a
2
. . . a
M
∈ V para b
1
b
2
. . . b
M
∈ V se, e somente se,
a
1
a
2
. . . a
M
b
M
∈ B(Y ). A função λ induz um SBC conjugado φ = λ
∞
de X
G
para Y [10,
Proposição 3.1.6]. Mais informações sobre esta construção de um SFT, partindo de um conjunto
finito F arbitrário, é apresentada em [20]. Em [21] é apresentado um algoritmo matricial que deter-
mina o Shannon cover a partir desta apresentação reescrita em forma de matriz.
34
CAPÍTULO 3
ALGORITMO PARA DETERMINAÇÃO DO
CONTEXTO À DIREITA: APLICAÇÃO NA
CONSTRUÇÃO DA m-SDP
No Capítulo 2 definimos um SFT como um sistema simbólico fechado especificado por um con-
junto proibido finito F. Mostramos que todo SFT é um SSR (ver também [10, Teorema 3.1.5]),
portanto podendo ser apresentado por um grafo G = (V, E, λ) direcionado. A rotulação de um ca-
minho bi-infinito em G gera uma seqüência que não contém fatores em F. Sistemas práticos para
armazenamento e transmissão de informação digital requerem a especificação de um conjunto F
[22],[23]. Um SFT pode ser especificado por conjuntos F distintos, mas entre estes há um único
conjunto O com número um mínimo de palavras proibidas, chamado a coleção mínima de palavras
proibidas [10, p.33].
Os métodos propostos para obtenção do Shannon cover (apresentação reduzida, determinística e
irredutível) de um SFT costumam ser divididos em duas etapas: inicialmente é gerada uma apresen-
tação determinística do SFT a partir do conjunto F [10, Teorema 3.1.5], [14], [24]; seguida por um
algoritmo para identificar as classes de vértices com mesmo contexto à direita e as conexões entre
classes (vértices da nova apresentação) por ramos.
O método descrito em [10] é o apresentado na Seção 2.4 do Capítulo 2. A função de transição
definida por este é simples de se calcular, mas o número de vértices do grafo inicial cresce exponen-
cialmente com o máximo comprimento das palavras em F, portanto isto o torna de pouco interesse
prático. Há algoritmos com complexidade linear que são desenvolvidos aplicando-se conceitos da
teoria de autômatos [14],[24]. Particularmente, no algoritmo descrito em [24], o conjunto de todos
os prefixos próprios das palavras do conjunto O formam os identificadores dos vértices da apresen-
tação inicial.
O algoritmo descrito em [14] constrói inicialmente um autômato não determinístico e incom-
pleto (o conjunto dos rótulos dos ramos que partem de um vértice é um subconjunto do alfabeto A),
tal que todas as palavras apresentadas por este possuem fatores em F. Um autômato determinís-
tico é obtido do não determinístico, fazendo-se dos vértices terminais os não terminais e vice-versa,
obtendo-se um autômato determinístico que apresenta a linguagem do SFT [17]. Removendo-se os
vértices não terminais deste autômato (com os ramos partindo deles e chegandoa eles), obtém-se um
grafo apresentando o SFT. A etapa intermediária deste algoritmo envolve a construção de um grafo
determinístico a partir de um não determinístico (ver accessible subset construction algorithm [17,
p.65]), procedimento que pode aumentar o número de estados em relação ao autômato inicial.
Neste capítulo apresentaremos um algoritmo para gerar o m-SDP de um SFT (o Shannon cover
para um SFT irredutível). A entrada do algoritmo é a coleção mínima de palavras proibidas O, a
partir desta são determinadas classes de palavras com o mesmo contexto à direita, entre aquelas
que pertencem ao conjunto W de todos os prefixos próprios de palavras em O. Estas classes de
palavras são empregadas como identificadores de vértices. A determinação destas classes é baseada
na manipulação de palavras em W e O, o que se diferencia da usual determinação de vértices com
mesmo contextoà direita a partir de uma apresentaçãoinicial [17], [19]. Oalgoritmo proposto associa
a cada palavra w ∈ W o conjunto de sufixos próprios das palavras em O que quando concatenados
com w geram uma palavra com um fator em O. Palavras em A
∗
com o mesmo contexto à direita
são determinadas pela igualdade de versões reduzidas destes conjuntos, assim podemos identificar as
palavras em W que possuem o mesmo contexto à direita, separando-as em classes de equivalência.
Definidas as classes de equivalência (ou os vértices da apresentação mínima), usamos uma função de
transição, baseada em uma definida em [24], para construirmos o Shannon cover. Mostraremos que
esta apresentação é isomorfa à componente essencial do grafo de contextos do SFT (Seção 3.3).
3.1 Alguns Conceitos e Definições
Iniciamos esta seção apresentando formalmente a coleção mínima de palavras proibidas. Uma
palavra w = w
1
. . . w
n
é dita uma proibição mínima se w /∈ L, mas w
1
. . . w
n−1
∈ L e w
2
. . . w
n
∈
L. A coleção de todas as proibições mínimas é única [10, p.12], de forma que se F ⊆ O e X
F
= X
O
então F = O. Um SFT com coleção mínima de palavras proibidas O tem memória M se o máximo
comprimento das palavras em O é M + 1. Na Seção 3.2, utilizamos a unicidade do conjunto O para
36
propor um procedimento que identifique palavras com o mesmo contexto à direita.
Seja {B
i
}
N
i=1
uma coleçãodesubconjuntosde Ae suponha que queremosclassificá-losde acordo
com seus contextos, onde o critério é a igualdade. Esta classificação pode serfeita a partir de {B
i
}
N
i=1
ou {B
′
i
}
N
i=1
, o que for mais conveniente, uma vez que, se B
j
= B
k
então B
′
j
= B
′
k
. Podemos esco-
lher uma das coleções e chamá-la de {D
i
}
N
i=1
. Caso tenhamos informações adicionais sobre o con-
junto {D
i
}
N
i=1
, estas podem ser utilizadas para simplificar a comparação. Como exemplo, suponha
que o conjunto G ⊆
N
i=1
D
i
é conhecido, esta informação poderá ser utilizada para simplificar o
processo de determinação de igualdade, que poderá ser realizado sobre o conjunto {D
i
\G}
N
i=1
no
lugar de {D
i
}
N
i=1
.
Dada uma linguagem qualquer L (não necessariamente fatorial), uma importante característica
de uma palavra w ∈ A
∗
é o seu conjunto sintático, definido como C(w) = {(x, y)|(x, y) ∈ A
∗
×
A
∗
e xwy ∈ L} [17, p. 210]. O complemento deste conjunto é C
′
(w) = {(p, s)|(p, s) ∈ A
∗
× A
∗
e
pws /∈ L}. Considerando L como a linguagem de um sistema simbólico fechada, dada uma palavra
w ∈ L, C
′
(w) = C
′
(w) ∪ ((A
∗
FA
∗
× A
∗
) ∪ (A
∗
× A
∗
FA
∗
)), já que para qualquer (p, s) ∈
((A
∗
FA
∗
×A
∗
) ∪(A
∗
×A
∗
FA
∗
)), pws /∈ L. Concluímos que ((A
∗
FA
∗
×A
∗
) ∪(A
∗
×A
∗
FA
∗
))
equivale ao conjunto G discutido no parágrafo anterior. Portanto, o conjunto sintático de uma palavra
w ∈ L pode ser especificado por um subconjunto de L × L, sendo este C
′
(w)\((A
∗
FA
∗
× A
∗
) ∪
(A
∗
× A
∗
FA
∗
)). Mostraremos na próxima seção que este conjunto não é a forma mais simples de
se representar o conjunto sintático de uma palavra. Como a linguagem de um SFT é fatorial, para
todo (p, s) ∈ C
′
(w)\((A
∗
FA
∗
×A
∗
) ∪ (A
∗
×A
∗
FA
∗
)) ⊆ L ×L, o conjunto {(p
′
p, ss
′
)|(p
′
, s
′
) ∈
(Lp
−1
) × (s
−1
L)} é um subconjunto de C
′
(w)\((A
∗
FA
∗
× A
∗
) ∪ (A
∗
× A
∗
FA
∗
)), o que motiva
à Definição 3.1.
Definição 3.1. Seja (p, s) ∈ L ×L, então [(p, s)] = {(p
′
p, ss
′
)|(p
′
, s
′
) ∈ (Lp
−1
) ×(s
−1
L)}. Como
extensão, seja A ⊆ L × L, se A = ∅ então [A] = {(p
′
, s
′
)|(p
′
, s
′
) ∈ [(p, s)] para todo (p, s) ∈ A},
caso contrário [A] = ∅.
Exemplo3.1. Seja A = {0, 1}e F = {011, 110, 001, 100}o conjuntoproibido do SFT de linguagem
L = B(X
F
). Assim, para (11, 0 ) ∈ L × L temos que [(1, 0)] = {(p, q) | p ∈ 1
∗
1 e q ∈ 0(0
∗
+
(10)
∗
)}, onde
′
+
′
indica união e w
∗
= {ε, w, ww, www, . . .}.
Segue diretamente da definição que (p, s) ∈ [(p, s)], pois ε ∈ L. A próxima definição apresenta
um subconjunto de C
′
(w)\((A
∗
FA
∗
× A
∗
) ∪ (A
∗
× A
∗
FA
∗
)) ⊆ L × L que determina C( w).
Definição 3.2. Um conjunto das restrições de w ∈ A
∗
, dada uma linguagem L, denominado de
37
C(w), satisfaz a equação [C(w)] = {(p, s)|(p, s) ∈ L × L e pws /∈ L} = C
′
(w)\((A
∗
FA
∗
× A
∗
) ∪
(A
∗
× A
∗
FA
∗
)).
Empregando a Definição 3.2 podemos escrever o conjunto sintático a partir do conjunto das
restrições como C(w) = { [C(w)] ∪ ((A
∗
FA
∗
× A
∗
) ∪ (A
∗
× A
∗
FA
∗
)) }
′
.
Exemplo 3.2. Considerandoo SFT apresentado no Exemplo 3.1, temos que C(0) = {(ε, 01), (ε, 11),
(11, ε), (10, ε), (1 , 0), (0, 1)} ou C(0) = {(ε, 01), (ε, 11), ( 11, 1), (11, 0), (11, ε), (10, ε), (1, 0),
(0, 1)}, já que [{(ε, 01), (ε, 11), (11, ε), (10, ε), (1, 0), (0, 1)}] = [{(ε, 01), (ε, 11), (11, 1), (11, 0),
(11, ε), (10, ε), (1, 0), (0, 1)}].
Exemplo 3.3. Se w /∈ L então para qualquer (p, s) ∈ L × L temos que pws /∈ L, portanto, um
possível conjunto das restrições para w é C(w) = {(ε, ε)}, pois que ε é prefixo e sufixo de qualquer
palavra. Assim, para w /∈ L temos que C
′
(w) = A
∗
× A
∗
.
No que segue, nosso interesse se restringe a três subconjuntos de C(w), são eles: C
l
(w) =
{(p, s)|p = ε e s = ε}, C
c
(w) = {(p, s)|p = ε e s = ε} e C
r
(w) = {(p, s)|p = ε e s = ε}, sendo
chamados de conjunto das restrições à esquerda, condicional e à direita, respectivamente.
Nota 3.1. Seja (ε, s
′
) ∈ [C(w)], portanto há (p, s) ∈ C(w) tal que (ε, s
′
) ∈ [(p, s)], assim p ∈ S( ε)
e s ∈ P(s
′
), logo p = ε. Como p = ε para todo (p, s) ∈ C
l
(w) ∪ C
r
(w), então (ε, s
′
) /∈ [C
l
(w) ∪
C
c
(w)], portanto (ε, s
′
) ∈ [C(w)\(C
l
(w) ∪ C
c
(w))] = [C
r
(w)].
Proposição 3.1. Para todo w ∈ L, (ε, s) ∈ [C
r
(w)] se, e somente se, s ∈ F
′
(w). Logo, [C
r
(w)] =
[C
r
(w
′
)] se, e somente se, F(w) = F(w
′
).
Demonstração: O contexto à direita de uma palavra w ∈ L pode ser escrito como F(w) =
L\F
′
(w), onde F
′
(w) = {s|ws /∈ L e s ∈ L}. Contudo, se s ∈ F
′
(w) então ws /∈ L, logo
(ε, s) ∈ [C(w)], da Nota 3.1 concluímos que (ε, s) ∈ [C
r
(w)]. Por outro lado, se (ε, s) ∈ [C
r
(w)]
então ws /∈ L, logo s ∈ F
′
(w). Concluímos que os conjuntos F(w) e F(w
′
) podem ser determinados
unicamente dos conjuntos [C
r
(w)] e [C
r
(w
′
)], respectivamente.
Podemos usar os conjuntos C
r
(w) para determinar os conjuntos F
′
(w) e F(w), já que F
′
(w) =
{s|(ε, s) ∈ [C
r
(w)]} e F(w) = {s|s ∈ L and (ε, s) /∈ [C
r
(w)]}, respectivamente. Na próxima seção
abordamos o problema de determinar palavras com o mesmo contexto à direita a partir dos conjuntos
C
r
(w).
38
3.2 Determinação de palavras com o mesmo contexto à direita
Provamos na Proposição 3.1 que a igualdade dos conjuntos [C
r
(w)] e [C
r
(w
′
)] implica que w e
w
′
têm o mesmo contexto à direita. Mas esta igualdade não assegura que C
r
(w) = C
r
(w
′
), já que,
em geral, estes conjuntos podem ser escritos de diferentes maneiras (ver Exemplo 3.2). Propomos
nesta seção uma construção particular para o conjunto C
r
(w), que nos permite determinar palavras
de mesmo contexto à direita pela simples igualdade deste conjunto.
Definição 3.3. Seja w ∈ L e O a coleção mínima de palavras proibidas de um SFT. Então C
r
O
(w) =
{(ε, s)|s ∈ ((S(w)\{ε})
−1
O)}, sendo o conjunto de todos os pares ordenados (ε, s) ∈ L ×L, |s| ≥
1, para os quais há p ∈ S(w)\{ε} tal que ps ∈ O.
Nota 3.2. Caso (S(w)\{ε}) ∩ P(OA
−1
) = ∅ então ws ∈ L para todo s ∈ L, assim C
r
O
(w) = ∅,
portanto C
r
O
(u) = ∅ para todo u ∈ S(w)\{ε}. Contudo, se C
r
O
(w) = ∅ então, para todo s ∈ L, ws
não possui fatores em O, implicando que C
r
(w) = ∅, uma vez que O é a coleção mínima de palavras
proibidas. Similarmente, se C
r
(w) = ∅ então C
r
O
(w) = ∅.
Na próxima proposição provaremos que [C
r
O
(w)] é um conjunto das restrições de uma palavra
w ∈ L.
Proposição 3.2. Seja w ∈ L e O a coleção mínima de palavras proibidas do SFT. Então [C
r
(w)] =
[C
r
O
(w)].
Demonstração: Da Nota 3.2 C
r
O
(w) = ∅ se, e somente se, C
r
(w) = ∅, assim [C
r
O
(w)] =
[C
r
(w)] = ∅ para este caso.
Suponha que C
r
O
(w) e C
r
(w) não são conjuntos vazios. Se (ε, s) ∈ [C
r
O
(w)] então ws /∈ L,
implicando que (ε, s) ∈ [C
r
(w)], logo [C
r
O
(w)] ⊆ [C
r
(w)]. Se supormos que (ε, s) ∈ [C
r
(w)],
então ws /∈ L, implicando que há p = p
1
. . . p
n
∈ S(w) e q = q
1
. . . q
m
∈ P(s) tal que pq /∈ L,
p
2
. . . p
n
q
1
. . . q
m
∈ L e p
1
. . . p
n
q
1
. . . q
m−1
∈ L, logo p
1
. . . p
n
q
1
. . . q
m
∈ O e ws tem um fator
em O, portanto (ε, s) ∈ [C
r
O
(w)], o que nos permite concluir que [C
r
(w)] ⊆ [C
r
O
(w)] e o resultado
segue.
Uma forma de cálculo dos C
r
O
(w) é por recursão. Para um dado w ∈ L, w = a
1
a
2
. . . a
n
,
o cálculo é feito do prefixo de menor comprimento não nulo (a
1
) para o de maior comprimento
39
(a
1
a
2
. . . a
n
), empregando a definição S(C
r
O
(w)) = {s | (ε, s) ∈ C
r
O
(w)}, temos que:
S(C
r
O
(a
1
)) = a
−1
1
O,
S(C
r
O
(a
1
a
2
)) = a
−1
2
S(C
r
O
(a
1
)) ∪ a
−1
2
O,
.
.
.
S(C
r
O
(a
1
a
2
. . . a
n
)) = a
−1
n
S(C
r
O
(a
1
. . . a
n−1
)) ∪ a
−1
n
O.
(3.1)
A prova desta relação segue pelo desenvolvimento do conjunto S(C
r
O
(w)):
S(C
r
O
(w)) = (S(w)\{ε})
−1
O
= (S(a
1
. . . a
n−1
)a
n
)
−1
O
= (S(a
1
. . . a
n−1
)a
n
∪ a
n
)
−1
O
= a
−1
n
S(a
1
. . . a
n−1
)
−1
O ∪a
−1
n
O
= a
−1
n
((S(a
1
. . . a
n−1
)\{ε})
−1
O) ∪ a
−1
n
O ∪a
−1
n
O
= a
−1
n
((S(a
1
. . . a
n−1
)\{ε})
−1
O) ∪ a
−1
n
O
= a
−1
n
S(C
r
O
(a
1
. . . a
n−1
)) ∪ a
−1
n
O.
Exemplo 3.4. Seja w = 1010 uma palavra pertencente a linguagem de um SFT com símbolos
no alfabeto A = {0, 1, 2} e especificado pelo conjunto O = {002, 100, 1011, 1012, 111, 112, 20,
211, 212}. Começamos calculando S(C
r
O
(1)) = 1
−1
O = {00, 011, 012, 11, 12}, seguimos calcu-
lando S(C
r
O
(10)) = 0
−1
S(C
r
O
(1))∪0
−1
O = {0, 11, 12, 02}, S(C
r
O
(101)) = 1
−1
S(C
r
O
(10))∪1
−1
O =
{1, 2, 00, 011, 012, 11, 12} e finalmente S(C
r
O
(1010)) = 0
−1
S(C
r
O
(101)) ∪ 0
−1
O = {0, 11, 12, 02}.
Observamos que quando (ε, s), (ε, s
′
) ∈ C
r
O
(w) e s
′
∈ P(s), implicando que (ε, s) ∈ [(ε, s
′
)],
então [C
r
O
(w)] = [C
r
O
(w)\(ε, s)]. Um conjunto C
r
(w) será escrito como
˜
C
r
(w) quando esta elimi-
nação de elementos não puder ser realizada.
Exemplo 3.5. A partir do conjunto C
r
O
(10) determinado no Exemplo 3.4,
˜
C
r
O
(10) = {(ε, s)|s ∈
{0, 11, 12}}, uma vez que 0 ∈ P( 02).
No próximo teorema mostraremos que palavras com o mesmo contexto à direita podem ser de-
terminadas pela igualdade dos seus conjuntos
˜
C
r
O
(w).
Teorema 3.3. Seja w, w
′
∈ L, então
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) se, e somente se, F(w) = F(w
′
).
Demonstração: Se
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) então [
˜
C
r
O
(w)] = [
˜
C
r
O
(w
′
)], o que das Proposições 3.2 e
3.1 implica que F(w) = F(w
′
).
40
Supondo que (ε, s) ∈
˜
C
r
O
(w) e (ε, s) /∈
˜
C
r
O
(w
′
) concluiremos que [
˜
C
r
O
(w)] = [
˜
C
r
O
(w
′
)], portanto
da Proposição 3.1 temos que F(w) = F(w
′
). Portanto, a hipótese que F(w) = F(w
′
) implica
que
˜
C
r
O
(w) =
˜
C
r
O
(w
′
), caso contrário, se
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) concluímos que F(w) = F(w
′
), o que
contradiz a hipótese. Se (ε, s) /∈ [
˜
C
r
O
(w
′
)] então [
˜
C
r
O
(w)] = [
˜
C
r
O
(w
′
)], logo consideraremos que
(ε, s) ∈ [
˜
C
r
O
(w
′
)]. Para que (ε, s) ∈ [
˜
C
r
O
(w
′
)] é necessário que exista (ε, s
′
) ∈
˜
C
r
O
(w
′
) tal que
s
′
∈ P(s) e |s
′
| < |s|. Já que (ε, s) ∈
˜
C
r
O
(w), então não há prefixos próprios u de s tal que
(ε, u) ∈
˜
C
r
O
(w), portanto, concluímos que (ε, s
′
) /∈ [
˜
C
r
O
(w)] e (ε, s
′
) ∈ [
˜
C
r
O
(w
′
)].
3.3 Construção da m-SDP
Nas últimas seções definimos o conjunto
˜
C
r
O
(w) e mostramos como utilizá-lo para determinar se
palavras em A
∗
possuem o mesmo contexto à direita. Nesta seção utilizamos
˜
C
r
O
(w) para construir
a apresentação determinística, de sincronização e reduzida do SFT. Mostraremos que esta apresen-
tação é isomorfa ao grafo dos contextos do SFT. Portanto, as propriedades demonstradas para a
apresentação propostas são estendidas para o grafo dos contextos.
O grafo dos contextos é uma apresentação determinística do SFT [10, p. 73] gerada a partir do
conjunto C = {F(w)|w ∈ L}, que é o conjunto de todos os contextos à direita de palavras em L (C
também pode ser interpretado como o conjunto dos vértices do grafo dos contextos). Há um ramo
neste grafo com rótulo a ∈ A partindo de um vértice I = F( w) ∈ C, se wa ∈ L, sendo o vértice
terminal J = F(wa) ∈ C. Pela aplicação deste procedimento a I ∈ C e a ∈ A obtemos o grafo dos
contextos do SFT. O conjunto C de um SFT é finito [10, Teorema 3.2.10], logo este procedimento é
realizável.
Seja G = ( V, E, L) a componente essencial do grafo dos contextos de um SFT. Propomos um
algoritmo alternativo para gerarG. Este algoritmo segueas etapas: (i) Encontrarum conjunto W ⊆ L
tal que V ⊆ {F(w)|w ∈ W}; (ii) determinar a partição P = {C
i
}
n
i=1
de W, satisfazendo a condição
w, w
′
∈ C
i
se, e somente se, F(w) = F(w
′
). Cada C
i
é um subconjunto de W contendo todas as
palavras deste com o mesmo contexto à direita. (iii) Definir uma função de transição de P × A para
P, como segue: seja C
i
∈ P e w ∈ C
i
, se wa ∈ L, a ∈ A, então há um ramo com rótulo a de C
i
para C
j
, tal que w
′
∈ C
j
onde F(w
′
) = F(wa); finalmente, extraímos a componente essencial do
grafo obtido no terceiro passo. Seguiremos determinando o conjunto W, propondo um método para
realizarmos a partição deste e definindo a função de transição.
Em [24] é apresentado um algoritmo para construir um autômato completo com um único vértice
41
inicial i e apresentando uma linguagem fatorial. Os vértices terminais deste autômato formam um
sub-grafo que apresenta a linguagem de um SSR. Este sub-grafo não é, necessariamente, essencial
nem reduzido. À cada vértice do conjunto V deste sub-grafo é associada uma palavra do conjunto
P(OA
−1
), da seguinteforma: todovértice I é alcançadoa partir de i por uma palavraw ∈ P(OA
−1
),
implicando que F(I) = F(w). Seja F(u) ∈ V, como o sub-grafo é uma apresentação do SSR, este
tem um caminho π, tal que i(π) = i, L(π) = u e F(t(π)) = F(u). Suponha que w ∈ P(OA
−1
) al-
cança t( π) a partir de i, então F(w) = F(u). Concluímos queo conjunto de vértices V da componente
essencial do grafo dos fatores é um subconjunto de {F(w)|w ∈ P(OA
−1
)}, portanto consideramos
W = P(OA
−1
).
A partição P é determinada pelos conjuntos
˜
C
r
O
(w) como especificado a seguir. Seja P
′
=
{C
′
i
}
m
i=1
uma partição de W, tal que: w, w
′
∈ C
′
i
se, e somente se,
˜
C
r
O
(w) =
˜
C
r
O
(w
′
). Empre-
gando o Teorema 3.3,
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) se, e somente se, F(w) = F(w
′
), o que nos leva a concluir
que P = P
′
.
Já definimos o conjunto W e a partição P. Antes de definirmos a função de transição apre-
sentaremos a relação que segue e por uma restrição no domínio desta relação obteremos a função de
transição.
Definição 3.4. Definimos a relação δ : P ×(A ∪ {ε}) −→ P ∪ {O} como
δ(C
i
, a) = {Q| fixado w ∈ C
i
, v ∈ Q, |v| = max
u∈T (wa)
|u|},
onde Q ∈ P ∪ {O} e T ( w) = S(w) ∩ (W ∪ O).
A imagem δ(C
i
, a) de (C
i
, a) é um elemento Q em P ∪ { O} associado com uma palavra fixada
w ∈ C
i
, tal que v ∈ Q é o maior sufixo de wa em W ∪ O. Segue desta definição que, se wa ∈ O
então δ(C
i
, a) = {O}.
O Teorema 3.6 demonstra, para qualquer (C
i
, a) ∈ P × (A ∪ {ε}), que o valor de δ(C
i
, a) não
depende da escolha de uma palavra w ∈ C
i
específica. O que nos permite concluir que δ é uma
função bem definida sobre o conjunto P × (A ∪ {ε}). Para demonstração deste teorema precisamos
dos resultados dos próximos dois lemas.
Lema 3.4. Para w, w
′
∈ L, seja
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) e a ∈ A, então
˜
C
r
O
(wa) =
˜
C
r
O
(w
′
a).
Demonstração: Pelo Teorema 3.3,
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) se, e somente se, F(w) = F(w
′
). Logo
waz ∈ L se, e somente se, w
′
az ∈ L, portanto F(wa) = F(w
′
a), ou
˜
C
r
O
(wa) =
˜
C
r
O
(w
′
a).
Lema 3.5. Seja w ∈ L e v o mais longo elemento em S(w) ∩ W, então
˜
C
r
O
(w) =
˜
C
r
O
(v).
42
Demonstração: Segue do processo de construção dos conjuntos
˜
C
r
O
(w) e
˜
C
r
O
(v) que
˜
C
r
O
(v) ⊆
˜
C
r
O
(w), uma vez que v ∈ S(w). Provaremos agora a inclusão reversa. Seja (ε, s) ∈
˜
C
r
O
(w), logo
existe p ∈ S(w)\{ε} tal que ps ∈ O, portanto p ∈ S(w) ∩ W. Já que v é a palavra mais longa em
S(w) ∩ W, então p ∈ S(v) e, portanto, (ε, s) ∈ C
r
O
(v). Se existe s
′
∈ P(s) para o qual (ε, s
′
) ∈
˜
C
r
O
(v), então(ε, s
′
) ∈
˜
C
r
O
(w), pois
˜
C
r
O
(v) ⊆
˜
C
r
O
(w), contradizendoa hipótesede que (ε, s) ∈
˜
C
r
O
(w),
logo (ε, s) ∈
˜
C
r
O
(v). Assim, concluímos que
˜
C
r
O
(w) ⊆
˜
C
r
O
(v), por fim
˜
C
r
O
(w) =
˜
C
r
O
(v).
Teorema 3.6. A relação δ é uma função bem definida.
Demonstração: Sejam w, w
′
∈ C
i
, C
i
um elemento de P, e a ∈ A. Como F(w) = F(w
′
), se
wa /∈ L então w
′
a /∈ L, logo δ(C
i
, a) = {O}. Portanto, consideremos que wa, w
′
a ∈ L, sendo v e
v
′
as palavras mais longas em S(wa) ∩W e S(w
′
a) ∩W, respectivamente. Do Lema 3.5 temos que
˜
C
r
O
(wa) =
˜
C
r
O
(v) e
˜
C
r
O
(w
′
a) =
˜
C
r
O
(v
′
). Por fim, do Lema 3.4
˜
C
r
O
(v) =
˜
C
r
O
(v
′
).
A Tabela 3.1 resume o algoritmo proposto para gerar uma apresentação de um SFT a partir do
seu conjunto O.
Exemplo 3.6. Seja O = {002, 100, 1011, 1012, 111, 112, 20, 211, 212}, o mesmo conjunto usado
no Exemplo 3.4. O conjunto dos prefixos próprios de O, P(OA
−1
), é W = {ε, 0, 1, 2, 00, 10,
101, 11, 21}. A Tabela 3.2 mostra os conjuntos
˜
C
r
O
(w) para w ∈ W, a partição P (ou classes
de equivalência) e o resultado do cálculo da função δ, mostrando-se as palavras mais longas em
S(wa) ∩ W para wa ∈ L. Se wa /∈ L, a entrada respectiva na tabela é preenchida com {O}. Pode-
mos observar que
˜
C
r
O
(2) =
˜
C
r
O
(10), assim o conjunto { 2, 10} ∈ W forma a classe C
4
. Prosseguindo,
obtemos as classes C
1
= {ε}, C
2
= {0}, C
3
= {1}, C
5
= {00} e C
6
= {11, 21, 101}. Portanto,
P = {{ε}, {0}, {1}, {2, 10}, {00}, {11, 21, 101}}. Observemos também que a palavra mais longa
em S(w1) ∩ W, w ∈ C
4
, é 21 se w = 2 ou 101 se w = 10, contudo {21, 1 01} ∈ C
6
, o que nos leva
a concluir que δ(C
4
, 1) = C
6
.
Como estamos interessados em uma apresentação de um SFT, podemos restringir a função δ
para A = {(C
i
, a)|δ(C
i
, a) ∈ P}. O que estamos fazendo é eliminando os ramos que incidem
no estado O, que por construção não possui ramos partindo dele, podendo ser removido do grafo
juntamente com os ramos que partem ou incidem nele, sem que com isso alteremos a linguagem do
SSR apresentada pelo grafo. Esta restrição é representada por δ|A e chamada função de transição,
mas por simplicidade de notação, iremos representá-la por δ. No próximo teorema mostraremos que
o grafo H gerado pelas linhas 1 a 16 do algoritmo descrito na Tabela 3.1 é isomorfo ao grafo dos
43
Tabela 3.1: Descrição do Algoritmo.
PASSO INSTRUCÃO
1. calcule W = P(OA
−1
);
2. faça P = ∅;
3. faça i = 0;
4. para cada w ∈ W
5. calcule
˜
C
r
O
(w);
6. se ∃ C
i
∈ P tal que w
′
∈ C
i
e
˜
C
r
O
(w) =
˜
C
r
O
(w
′
)
7. faça C
i
= C
i
∪ {w};
8. se não
9. faça i = i + 1;
10. crie C
i
em P;
11. faça C
i
= {w};
12. para cada (C
i
, a) ∈ P × A
13. se δ(C
i
, a) ∈ P
14. crie um ramo com rótulo a de C
i
para δ(C
i
, a);
15. se não
16. não crie um novo ramo;
17. faça G
′
= (V
′
, E
′
, λ
′
) a componente essencial do grafo
gerado nos passos 12-16;
18. saída G
′
= (V
′
, E
′
, λ
′
);
Os passos 4-11 determinam a partição P. Os passos 12-16 calculam a função de transição. Denotaremos por H o grafo dos contextos
gerado pelas linhas 1-16 do algoritmo.
Tabela 3.2: Cálculo das classes de equivalência e da função δ(C
i
, a), para C
i
∈ P e a ∈ A.
Cálculo das Classes δ(C
i
, a) - {Palavra mais longa em S(wa) ∩ W}
w ∈ W {s|(ε, s) ∈
˜
C
r
O
(w)} Classes δ(C
i
, 0) − {v} δ(C
i
, 1) − {v} δ(C
i
, 2) − {v}
ε ∅ C
1
C
2
− {0} C
3
− {1} C
4
− {2}
0 02 C
2
C
5
− {00} C
3
− {1} C
4
− {2}
1 00, 11, 12, 01 1, 012 C
3
C
4
− {10} C
6
− {11} C
4
− {2}
2 0, 11, 12 C
4
{O} C
6
− {21} C
4
− {2}
00 2, 02 C
5
C
5
− {00} C
3
− {1} {O}
10 0, 11, 12 C
4
{O} C
6
− {101} C
4
− {2}
11 1, 2, 00, 011, 012 C
6
C
4
− {10} {O} {O}
21 1, 2, 00, 011, 012 C
6
C
4
− {10} {O} {O}
101 1, 2, 00, 011, 012 C
6
C
4
− {10} {O} {O}
44
contextos, portanto as componentes essenciais destes também são isomorfas.
Teorema 3.7. O grafo H é isomorfo ao grafo dos contextos do SFT.
Demonstração: Iniciamos definindo a função Φ : C → P como C
i
= Φ(F(w)), então C
i
é
a classe que contém a palavra mais longa em S(w) ∩ W. Seguimos provando que Φ é uma função
sobrejetiva, injetiva e é um homomorfismo, respectivamente.
Suponha que F(w) = F(w
′
). Dos Lemas 3.4 e 3.5, se v e v
′
são as palavras mais longas em
S(w) ∩ W e S(w
′
) ∩ W, respectivamente, então F(v) = F(v
′
), implicando que v e v
′
pertencem à
mesma classe de equivalência de P, logo Φ(F(w)) = Φ(F(w
′
)). Concluímos que Φ é uma função
bem definida.
Para todo C
i
∈ P e qualquerw ∈ C
i
, temos quew ∈ L e Φ(F(w)) = C
i
, ou seja, Φ é sobrejetiva.
Suponha que Φ(F(w)) = Φ(F(w
′
)), isto implica que as palavras mais longas em S(w) ∩ W e
S(w
′
) ∩ W pertencem à mesma classe de equivalência. Do Lemma 3.5 isto implica que
˜
C
r
O
(w) =
˜
C
r
O
(w
′
) e do Teorema 3.3 temos que F(w) = F(w
′
). Concluímos que Φ é injetiva.
A classe δ(Φ(F(w)), a) contém a palavra mais longa v em S(ua) ∩ W, onde u é a palavra mais
longa em S(w) ∩W. Supondo que v
′
pertence a S(wa) ∩W. Se v
′
= ε, podemos escrever v
′
= u
′
a,
onde u
′
∈ S( w) ∩ W, já que o prefixo de um elemento em W pertence a W. Isto implica que u
′
é
um sufixo de u, logo v
′
= u
′
a ∈ S(ua) ∩ W. Como S(ua) ⊆ S(wa) então v ∈ S(wa), logo v é a
palavra mais longa em S(wa) ∩ W e, portanto, δ(Φ(F(w)), a) = Φ (F(wa)). Concluímos que Φ é
um homomorfismo.
Corolário 3.8. O grafo G
′
é uma apresentação do SFT.
Demonstração: Devido ao isomorfismo entre o grafo H e o grafo dos contextos, qualquer ca-
minho bi-infinito (. . . e
−1
e
0
e
1
. . .) em H está associado a um único caminho bi-infinito (. . . f
−1
f
0
f
1
. . .) no grafo dos contextos e vice-versa, tal que Φ(t(e
j
)) = t(f
j
), Φ
−1
(t(f
j
)) = t(e
j
) e e
j
, f
j
possuem o mesmo rótulo. Estes caminhos também estão presentes nas componentes essenciais G
′
=
{V
′
, E
′
, λ
′
} e G = {V, E, λ} de H e do grafo dos contextos, respectivamente, permitindo a definição
do isomorfismo Ψ : V → V
′
entre G e G
′
, tal que Ψ = Φ|V.
A Figura 3.1 mostra o grafo obtido diretamente da Tabela 3.2 pela conexão das classes de equiva-
lência (vértices) de acordo com a função de transição δ. A Figura 3.2 mostra a componente essencial
do grafo apresentado na Figura 3.1.
O próximo lema expõe uma propriedade de G
′
que nos permitirá provar no Teorema 3.11, que
G
′
é o mínimo SDP, ou o Shannon cover para um SFT irredutível.
45
Lema 3.9. Seja π um caminho em G
′
conectando os vértices C
i
= i(π) e C
j
= t(π), para o qual
L(π) = z. Para qualquer w ∈ C
i
, a palavra mais longa em S(wz) ∩ W pertence a C
j
.
Demonstração: A prova é por indução no comprimento |z|. Inicialmente, seja |z| = 0, logo
z = ε, portanto wz = wε = w, que é a palavra mais longa em S(wε) ∩ W, concordando com a
equação δ(C
i
, ε) = C
i
.
Consideremos que a afirmação é verdadeira para |z| = n. Seja τα um caminho em G
′
, i(τα) =
C
i
e z = L( τ α) = L(τ)L(α) = ua, tal que |u| = n e a ∈ A. Se u
′
é a palavra mais longa em
S(wu)∩W, entãoconcluímosda hipótese indutiva queu
′
∈ t(τ). A partir da definiçãode δ, a palavra
mais longa em S(u
′
a) ∩W pertence a δ( t(τ), a). Caso S(u
′
a) ∩W = {ε}então S(wz) ∩W = {ε},
do contrário, se x
′
a ∈ S(wz) ∩ W então x
′
∈ S( u
′
) e, portanto, x
′
a ∈ S(u
′
a) ∩ W, o que é uma
contradição. Assim, o lema é válido para este caso.
Consideremos que a palavra mais longa em S(u
′
a) ∩ W seja não nula e igual a q
′
a. Agora, seja
qa a palavra mais longa em S(wz) ∩ W, então q ∈ S(wu) ∩W (já que todo prefixo de uma palavra
em W pertence a W), isto implica que q ∈ S(u
′
), logo q ∈ S(q
′
). Por fim, como u
′
a ∈ S(wz), a
palavra mais longa em S(u
′
a) ∩ W pertence a S(wz) ∩ W, portanto q
′
∈ S(q). Concluímos que
q
′
a = qa.
Proposição 3.10. G
′
= (V
′
, E
′
, L
′
) é uma apresentação determinística, de sincronizaçãoe reduzida.
Demonstração: Como o grafo dos contextos é determinístico, todo sub-grafo dele também é
determinístico. Já que G
′
é isomorfo a G, então G
′
é determinístico.
Prosseguiremos provando que G
′
é de sincronização. Seja M o máximo comprimento de uma
palavraem W, logo para todo w, u ∈ L, |u| ≥ M, as palavras mais longasem S(wu)∩W e S(u)∩W
são iguais. Portanto, segue do Lema 3.9 que todo z ∈ L, |z| ≥ M , z é uma palavra de sincronização
C
1
C
5
C
3
C
4
C
6
C
2
1
0
1
0
2
0
0
1
2
2
2
1
0
1
Figura 3.1: Grafo obtido da Tabela 3.2.
46
C
5
C
3
C
4
C
6
1
0
0
2
2
1
0
1
Figura 3.2: Componente essencial do grafo apresentado na Figura 3.1.
de G
′
. Suponha que há um vértice C
i
∈ V
′
que não possui uma palavra de sincronização, então
todo caminho π em G
′
, t(π) = C
i
, tem comprimento menor que M. Considerando os caminhos em
G
′
com vértice terminal C
i
, seja π
′
um entre os mais longos destes caminhos, então não há ramos
com vértice terminal i(π
′
). Como G
′
é uma grafo essencial, concluímos que há uma palavra de
sincronização para todo vértice de G
′
.
Agora provaremos que G
′
é reduzido. Seja z ∈ L, |z| ≥ M , uma palavra de sincronização
para C
i
∈ V
′
. Portanto, a palavra mais longa em S(z) ∩ W pertence a C
i
. Segue do Lema 3.5,
que
˜
C
r
O
(z) =
˜
C
r
O
(u) para todo u ∈ C
i
, logo, do Teorema 3.3 obtemos que F(z) = F(u). Como
F(z) = F(C
i
), podemos concluir que F(C
i
) = F(u). Portanto, G
′
é reduzido, já que para todo
u ∈ C
i
e u
′
∈ C
j
, F(u) = F(u
′
) se, e somente se, i = j.
Teorema 3.11. G
′
= (V
′
, E
′
, L
′
) é o Shannon cover de um SFT irredutível e o mínimo SDP de um
SFT redutível.
Demonstração: Da Proposição 2.2 todas as SDPs reduzidas de um SSR são isomorfas, portanto,
segue da Proposição 3.10 que G
′
é a mínima SDP. Como já havíamos definido, o Shannon cover é a
única (por um mapeamento isomorfo) apresentação determinística, reduzida e irredutível de um SSR
irredutível, de [10, Teorema 3.4.17] este também é de sincronização. Logo, G
′
é o Shannon cover de
um SFT irredutível.
3.4 Análise da complexidade do algoritmo
Inicialmente analisaremos a complexidade para obter-se o conjunto P dado o conjunto W, o que
equivale à especificaçãodos vértices. Em seguida, analisaremosa complexidade do cálculoda função
47
de transição.
3.4.1 Complexidade do Cálculo do Conjunto P
Para determinarmos P dado o conjunto W, utilizaremos o Teorema 3.3 para determinarmos as
palavras em W com mesmo contexto à direita. O cálculo de P será dividido em três etapas: (1)
cálculo dos conjuntos S(C
r
O
(w)) para todo w ∈ W; (2) cálculo dos conjuntos S(
˜
C
r
O
(w)) para todo
w ∈ W; (3) determinara partiçãodo conjuntoW (pela relação de equivalência: w ∼ w
′
se, e somente
se
˜
C
r
O
(w) =
˜
C
r
O
(w
′
)).
Complexidade do cálculo dos conjuntos C
r
O
(w)
Consideremos a
i
∈ A e a
1
a
2
. . . a
n
∈ W. Do cálculo recursivo apresentado na Equação 3.1,
|S(C
r
O
(a
1
))|é proporcional a |O|, |S(C
r
O
(a
1
a
2
))| ≤ |a
−1
2
S(C
r
O
(a
1
))|+|a
−1
2
O| é proporcional a 2·|O|,
seguindo este raciocínio, |S(C
r
O
(a
1
. . . a
n
))| ≤ |a
−1
n
S(C
r
O
(a
1
. . . a
n−1
))| + |a
−1
n
O| é proporcional
a n · |O|, sendo que n ≤ M, onde M + 1 é maior comprimento das palavras em O. Assim, a
cardinalidade dos conjuntos S(C
r
O
(w)), conseqüentemente dos conjuntos C
r
O
(w), é proporcional a
|O|, com coeficiente de proporcionalidade não superior a M. Portanto, a complexidade assintótica
para o cálculo de C
r
O
(w
1
. . . w
n
), dado C
r
O
(w
1
. . . w
n−1
), é O(|O|).
Pela definição do conjunto W obtemos a relação P( W) = W, assim, aplicaremos a expressão
recursiva (3.1) para determinarmos o conjunto {S(C
r
O
(w)) | w ∈ W}. O que implica em calcularmos
M − 1 conjuntos S(C
r
O
(w)) (já que S(C
r
O
(ε)) = ∅). Portanto, a complexidade assintótica para o
cálculo do conjunto {C
r
O
(w) | w ∈ W} é O(|O| · |W|).
Complexidade do cálculo dos conjuntos
˜
C
r
O
(w)
A determinação de
˜
C
r
O
(w) a partir de C
r
O
(w) pode ser realizada usando-se uma árvore enraizada
rotulada, de construção especificada a seguir. Dos nós não-terminais da árvore, partem no máximo
|A| ramos com rótulos em A, dispostos em ordem lexicográfica definida pelos rótulos. O rótulo de
um caminho começando no nó raiz da árvore é a seqüência dos rótulos dos ramos que constituem
o caminho. A partir das seqüências de menor comprimento, marca-se como um nó terminal o nó
alcançado por um caminho com rótulo em C
r
O
(w). Os elementos em S(
˜
C
r
O
(w)) são associados a
nós terminais (folhas) da árvore. Seqüências em S(C
r
O
(w))\S(
˜
C
r
O
(w)) não podem ser associadas a
caminhos na árvore.
Como exemplo, consideremos o conjunto S(C
r
O
(101)) = {1, 2, 00, 011, 012, 11, 12} apresentado
no Exemplo 3.4. A árvore associada a este é mostrada na Figura 3.3. Ao percorrermos a árvore
48
utilizando o elemento 11 ou 12, iremos alcançar a folha 1, o que indica que estes elementos possuem
um prefixo próprio no conjunto S(C
r
O
(101)), portanto as folhas 11 e 12 não são criadas, o que é
representado na Figura 3.3 pelas linhas pontilhadas.
0
00
01
011
012
1
11
12
2
Figura 3.3: Árvore para o cálculo do conjunto
˜
C
r
O
(101).
Dado um conjunto S(C
r
O
(w)), w ∈ W, a complexidade deste procedimento é proporcional ao
número de caminhos que iremos percorrer na árvore, ou seja, O(|O|). Como este cálculo será reali-
zado para todos os elementos do conjunto W, a complexidade desta etapa é O(|O| · |W|).
Complexidade do cálculo das classes de equivalência
Para determinarmos os conjuntos
˜
C
r
O
(w) que são iguais, podemos, seguindo a mesma ordem
lexicográfica, sobrepor as árvores dos conjuntos
˜
C
r
O
(w) e indicar nos nós os conjuntos
˜
C
r
O
(w) para
os quais estes nós são folhas. Este processo pode ser realizado simultaneamente com o cálculo dos
conjuntos
˜
C
r
O
(w). Os conjuntos
˜
C
r
O
(w) iguais são os que ocorrem nos mesmos nós. A Figura 3.4
mostra a árvore associada ao Exemplo 3.6.
As classes de conjuntos iguais são as mesmas calculadas na Tabela 3.2. A complexidade do
algoritmo é proporcional ao número de nós e a cardinalidade do conjunto W, ou seja, O(|O|· |W|).
3.4.2 Complexidade do Cálculo da Função de Transição
Para a determinação da função de transição, δ, empregamos uma variação da
função de falha
definida em [24], que chamaremos de f e a definiremos a seguir.
Definição 3.5. Seja C
ε
a classeem P que contéma palavraε. Definimosa função f : P\{ C
ε
} −→ P,
tal que, dado v = au, a ∈ A, uma das palavras de menor comprimento em C
i
, então f(C
i
) é o
conjunto em P que contém o mais longo sufixo de u em W.
49
˜
C
r
O
(ε)
˜
C
r
O
(10),
˜
C
r
O
(2)
0
˜
C
r
O
(1),
˜
C
r
O
(11),
˜
C
r
O
(21),
˜
C
r
O
(101)
00
01
˜
C
r
O
(1),
˜
C
r
O
(11),
˜
C
r
O
(21),
˜
C
r
O
(101)
011
˜
C
r
O
(1),
˜
C
r
O
(11),
˜
C
r
O
(21),
˜
C
r
O
(101)
012
˜
C
r
O
(0),
˜
C
r
O
(00)
02
˜
C
r
O
(11),
˜
C
r
O
(21),
˜
C
r
O
(101)
1
˜
C
r
O
(1),
˜
C
r
O
(2),
˜
C
r
O
(10)
11
˜
C
r
O
(1),
˜
C
r
O
(2),
˜
C
r
O
(10)
12
˜
C
r
O
(00),
˜
C
r
O
(11),
˜
C
r
O
(21),
˜
C
r
O
(101)
2
Figura 3.4: Árvore para o cálculo das classes de equivalência.
Dado o conjunto P, a função de transição δ será calculada primeiramente para as classes em
P que contêm as menores palavras em W. Assim, começamos pela classe que contém a palavra
ε, em seguida calculamos δ para as classes que contêm as palavras de comprimento um, e assim
sucessivamente. Finalizamos quando a função δ tiver sido calculada para todas as classes do conjunto
P.
O algoritmo apresentado na Tabela 3.3 calcula a função δ para todo C
i
∈ P e a ∈ A. Seguiremos
definindo algumas notações que são empregadas neste algoritmo. Para todo v ∈ W ∪ O, chamamos
de C
v
a classe em P ∪ { O} que contém v. Dado um conjunto de palavras A, chamaremos de A
(i)
o
subconjunto de palavras em A de comprimento i.
No algoritmo da Tabela 3.3 o conjunto O pertence a imagem da função de transição δ, o que
não ocorre para o algoritmo na Tabela 3.1. Isto se deve ao uso da função de falha, mas não acarreta
em acréscimo da complexidade, pois o vértice associado ao conjunto O não possui ramos de saída,
portanto, dispensandoqualquerverificação, podemos excluí-lo ao final do algoritmo, juntamente com
os ramos que incidem neste.
Com o conhecimento das classesde equivalênciae indexaçãodestas através de seus elementos de
menor comprimento, as operações das linhas 7,10,11 e 21 possuem complexidade O(|P|). O cálculo
da função de transição, δ, para qualquer C
i
∈ P tem complexidade assintótica O(|A|). Assim, o
cálculo de δ para todos os elementos de P tem complexidade assintótica O (|A| · |P|). Portanto, a
etapa de cálculo da função de transição, quando realizada pelo algoritmo apresentado na Tabela 3.3,
50
Tabela 3.3: Cálculo da função de transição δ.
PASSO INSTRUCÃO
1. para cada a ∈ A
2. se a ∈ W
3. faça δ(C
ε
, a) = C
a
;
4. faça f(C
a
) = C
ε
;
5. se não
6. faça δ(C
ε
, a) = C
ε
;
7. faça P
1
= W\ C
ε
;
8. enquanto P
1
= ∅
9. i = min{|w| : w ∈ P
1
};
10. faça P
2
= P
(i)
1
;
11. faça P
1
= P
1
\
v∈P
2
C
v
;
12. enquanto P
2
= ∅
13. seja v ∈ P
2
;
14. para cada a ∈ A
15. se va ∈ W ∪ O
16. faça δ(C
v
, a) = C
va
;
17. se va ∈ W
18. faça f(C
va
) = δ(f(C
v
), a);
19. se não
20. faça δ(C
v
, a) = δ(f(C
v
), a);
21. faça P
2
= P
2
\C
v
;
tem complexidade assintótica O(|A|·|P|).
3.4.3 Complexidade do Algoritmo para Determinação da m-SDP
Empregamos duas etapas para determinação da m-SDP através da técnica apresentada. Na
primeira, determinamos P por meio de um algoritmo de complexidade assintótica O(|O| · |W|).
Na segunda, calculamos a função de transição δ, utilizamos para isto um algoritmo de complexidade
assintótica O(|A| · |P|). Concluímos que as duas etapas podem ser realizadas por um algoritmo de
complexidade O(|O| · |W|) + O(|A| · |P|).
51
CAPÍTULO 4
DETERMINAÇÃO DO CONTEXTO À
DIREITA PARA PFT IRREDUTÍVEL:
APLICAÇÃO NA CONSTRUÇÃO DE
APRESENTAÇÕES DETERMINÍSTICAS E
REDUZIDAS
Os códigos restritivos são comumente empregados em sistemas que utilizam equalização com
resposta parcial e detecção por seqüência, sendo usualmente chamados em sistemas de gravação
magnética de
códigos restritivos para aumento de distância
. O seu emprego visa aumentar a distância
mínima na saída do canal com interferência inter-simbólica pela proibição de um número finito de
seqüências binárias. Como comentado no Capítulo 2, o estudo e projeto destes codificadores pode
ser realizado aplicando-se a teoria de dinâmica simbólica. Lembrando que, para o caso em que o
conjunto das seqüências proibidas é finito, os sistemas simbólicos fechados são sistemas simbólicos
regulares de memória finita (SFT).
As restrições de um SFT são globais, ou seja, estas independem da coordenada na seqüência
bi-infinita. No entanto, restrições têm sido apresentadas para as quais as proibições ocorrem de
forma periódica, sendo chamadas de
restrições periódicas
, e.g., a restrição TMTR (do inglês time-
varying maximum-transition-run) proíbe que a palavra 111 seja iniciada em índices ímpares de uma
seqüência. Os sistemas simbólicos dinâmicos periódicos ou PFT (do inglês periodic shift of finite
type) foram introduzidos em [25] como a classe de sistemas simbólicos fechados adequada para
modelagem destas restrições (se for possível descrevê-las por um conjunto finito), sendo um PFT
Cod.
Restritivo
Cod. CCE
Sistemático
Concat.
Separ.
Dec. CCE
Sistemático
Dec.
Restritivo
Cod. Restritivo
da Paridade
Dec. Restritivo
da Paridade
Canal
Paridade Paridade
Figura 4.1: Diagrama de concatenação reversa.
especificado por um conjunto finito de palavras proibidas indexadas (índices representando fases) e
um período T .
Restrições periódicas também aparecemem aplicaçõesque empregamcodificaçãoconjunta CCE/
restritiva. No Capítulo 1 mencionamos a possibilidade de melhorar o desempenho de um sistema de
comunicações adaptando-se a seqüência transmitida às características do canal. Isto pode ser obtido
pelo projeto de códigos que tanto possam corrigir como restringir a seqüência transmitida, no en-
tanto, na prática cascateia-se os codificadores. Apresentamos na Figura 1.1 um arranjo padrão para
os codificadores. A desvantagem deste arranjo é a possibilidade de propagação de erros pelo deco-
dificador restritivo antes que estes sejam corrigidos pelo decodificador CCE. Como alternativa há a
concatenação reversa
, mostrada na Figura 4.1, onde a posição dos codificadores é invertida, neste
caso algumas precauções devem ser seguidas para evitar que as restrições impostas às seqüências
não sejam violadas. Isto é obtido pelo uso de um
codificador CCE sistemático
e um
codificador
restritivo da paridade
com um algoritmo de decodificação que limite a propagação de erros. A saída
do codificador restritivo da paridade é concatenada com a saída do
codificador CCE sistemático
pelo
concatenador
, com a possível inserção de bits entre as seqüências de saída, possibilitando que a se-
qüência resultante satisfaça a restrição. Na decodificação, o
separador
envia os bits de informação
para o
decodificadorCCE sistemático
e os bits de paridade codificados para o
decodificadorrestritivo
da paridade
antes de irem para o decodificador CCE sistemático. Este processo possibilita a correção
de parte dos erros gerados pelo canal antes que a seqüência recebida passe pelo decodificador restri-
tivo, o que reduz a propagação de erros na decodificação restritiva. Quando o codificador restritivo
tiver alta taxa, isto será mantido por este sistema, já que a seqüência de paridade é curta quando
comparada com a seqüência de informação.
Consideremos que não seja empregada a métrica de Hamming na decodificação (soft-decision
decoding). A informação para decodificação associada aos bits de informação é diretamente disponi-
53
bilizada para o decodificador CCE, já que o codificador CCE é sistemático e só os bits de paridade
passampor um codificador restritivo antes de seremenviados ao canal. Neste caso, a informação para
decodificação contida na seqüência de paridade gerada pelo codificador CCE terá que ser extraída de
uma seqüência codificada pelo codificador restritivo da paridade e com possíveis erros gerados pelo
canal. Este procedimento pode ser simplificado e realizado com maior precisão se o codificador res-
tritivo da paridade for sistemático. Isto poderia reduzir a taxa do codificador restritivo da paridade,
o que só estaria relacionado à pequena porção da seqüência codificada relativa aos bits de paridade,
tendo pouca representatividade na taxa do sistema completo.
Relativo a um codificador restritivo da paridade sistemático, Wijngoorden e Immink sugeriram o
arranjo apresentado na Figura 4.2 [26]. A idéia proposta é o codificador restritivo gerar seqüências
com posições não restritas, ou seja, nestas posições o bit pode assumir arbitrariamente o valor 0 ou 1
sem violar a restrição, portanto os bits de paridade gerados pelo codificador CCE sistemático podem
ser inseridos nestas posições (realizado pelo bloco
Insere
da Figura 4.2) sem violar a restrição. O
sistema obtido pelo conjunto de todas as seqüências bi-infinitas com
posições irrestritas
geradas pelo
arranjo proposto por Wijngoorden e Immink forma um PFT [3].
Uma das possibilidades no projeto de um sistema que utilize codificação conjunta, como o re-
presentado na Figura 4.2, é a construção do maior subsistema de um SFT S, tal que toda posição
módulo T em U é irrestrita, sendo U um subconjunto de T . Este sistema é chamado de
subsis-
tema
(U, T )
-irrestrito
de S. Conhecendo-se este subsistema, podemos calcular a entropia topológica
do conjunto de seqüências que satisfazem uma dada restrição e são irrestritas em um conjunto de
posições. Aplicando-se os procedimentos para construção de códigos de linha, podemos projetar
codificadores para este subsistema; como estes procedimentos atuam em uma apresentação do sub-
sistema, deve-se procurar apresentações com número mínimo de vértices.
Neste capítulo apresentaremos conceitos que serão empregados para determinar uma apresen-
tação determinística e reduzida de um PFT irredutível. Isto será possível pois a linguagem de um
Cod.
Restritivo
Cod. CCE
Sistemático
Insere
Separ.
Dec. CCE
Sistemático
Dec.
Restritivo
Canal
Paridade Paridade
Figura 4.2: Diagrama de concatenação Wijngaarden-Immink.
54
PFT é regular [25]. Para isto, iremos generalizar a idéia apresentada no Capítulo 3, para uma coleção
mínima periódica de palavras proibidas e para construção do grafo a partir de classes obtidas de uma
lista indexada de palavras da linguagem.
4.1 Alguns Conceitos e Definições
Os PFT são sistemas simbólicos dinâmicos fechados com restrições variantes no tempo, sendo
os sistemas dinâmicos simbólicos adequados para representar conjunto de seqüências que proíbem a
ocorrência de palavras em coordenadas periódicas da seqüência módulo um período T .
Determinado um inteiro positivo T , seja F uma coleção finita de palavras em A
∗
, tal que, para
cada w
i
∈ F é associado um inteiro k
i
em {0, 1, . . . , T − 1} que recebe o nome de
fase
. Descreve-
mos o conjunto F por F = {(w
1
, k
1
), (w
2
, k
2
), . . . , (w
n
, k
n
)} e o chamamos de
conjunto proibido
periódico
. As restrições associadas a uma fase k são escritas por F
(k)
= {w| (w, n) ∈ F e n = k}.
Seja uma palavra finita w um fator de uma seqüência finita ou infinita x na coordenada i, portanto
w = x
[i,i+|w|−1]
, isto é representado por w ≺
i
x, o contrário é representadopor w ⊀
i
x. Escrevemos
w ≺ x quando uma palavra w é um fator de uma seqüência x, sem considerar uma coordenada es-
pecífica, o contrário é representado por w ⊀ x. Uma palavra w é um fator próprio de uma seqüência
x, quando w ≺ x e w = x. Um PFT com período T e conjunto proibido periódico F, representado
por X
{F,T }
, é definido a seguir.
Definição 4.1. Uma seqüência bi-infinita x pertence a X
{F,T }
se, e somente se, existe um inteiro
k ∈ {0, . . . , T − 1} tal que, para todo inteiro i, se w ≺
i
σ
k
(x) então w /∈ F
(i mod T )
.
Para todo PFT é possível construir um grafo G = (V, E, λ) que o apresente, ou seja, um PFT é
um SSR [25, Teorema 1]. G é dito T -partite se V pode ser dividido em T subconjuntos D
0
, D
1
, . . . ,
D
T −1
, tal que, qualquer ramo que parte de um vértice em D
i
alcança um vértice em D
i+1 mod T
.
Para I, J ∈ V, o número de ramos que partem de I e alcançam J é A
IJ
. A
matriz adjacência
de G
é quadrada, de ordem |V| e é denotada por A
G
=
A
IJ
. O
período de um vértice
I, representado
por per(I), é o máximo divisor comum dos inteiros n para os quais (A
n
G
)
II
> 0. Caso este número
não exista, então denota-se per(I) = ∞. O
período de uma matriz
A, representado por per(A), é o
máximo divisor comum dos números per(I) que são finitos, ou é ∞ se per(I) = ∞ para todo I. O
período de um grafo
G, representado por per(G), é o período de A
G
, i.e, per(G) per(A
G
). Se G
é irredutível, todos os estados têm o mesmo período [10, Lema 4.5.3], se per(A
G
) = T , então G é
T -partite e os conjuntos D
1
, D
2
, . . . , D
T −1
são as T
classes periódicas
do grafo.
55
Se o PFT é irredutível, podemos determinar seu Shannon cover aplicando métodos convencionais
para construção de grafos determinísticos a partir de conjuntos de palavras proibidas seguidos de al-
goritmos de minimização [25], [3]. Em nossa abordagem, sempre estaremos considerando o período
como sendo o do Shannon cover, portanto, lembramos que parte dos resultados só são válidos para
PFT irredutíveis, o que deixaremos claro pelo enunciado destes.
Associado ao conceito de restrição por fase está o de linguagem por fase, que empregaremos para
descrever as restrições de palavras em A
∗
para uma fase específica, como também na obtenção de
propriedades de apresentações do PFT.
Definição 4.2. Seja L
x
⊆ {0, . . . , T −1} o conjunto de deslocamentos de um ponto x ∈ A
Z
tal que
∀i ∈ Z e ℓ
x
∈ L
x
se v ≺
i
σ
ℓ
x
(x) então v /∈ F
(i mod T )
. Definimos uma linguagem associada com
a fase k como L
(k)
= {u ≺
j
σ
ℓ
x
(x)| x ∈ X
{F,T }
, ℓ
x
∈ L
x
e j ≡ k mod T }.
Um conceito similar ao de coleção mínima de palavras proibidas de um SFT existe para um
PFT, sendo chamado de
conjunto mínimo periódico de palavras proibidas
, contendo os elementos
(w, k) ∈ A
∗
× {0, . . . , T − 1}, w = w
0
w
1
. . . w
n
, que não pertencem a linguagem L
(k)
mas com
todos os fatores próprios u ≺
i
w pertencendo a linguagem L
(k+i mod T )
. Portanto, (w, k) ∈ O se,
e somente se, w /∈ L
(k)
, w
[0,|w|−2]
∈ L
(k)
e w
[1,|w|−1]
∈ L
(k+1 mod T )
. Em [25, Teorema 4] é
demonstrado que O é único (sendo T o período do Shannon cover).
Exemplo4.1. Como exemploda dependênciada linguagem coma fase, consideremosO = {(101, 0),
(111, 1)} e T = 2. Observe que 11100 ∈ L
(0)
e 1010 ∈ L
(1)
, no entanto, 1010 /∈ L
(0)
e
11100 /∈ L
(1)
.
Motivados pela Definição 4.2, quando queremos enfatizar que w ∈ L
(k)
escrevemos (w, k). Se
(w, k) não é definido, logo w /∈ L
(k)
, implicando que os elementos em O
(k)
proíbem a ocorrência
de w, o que não impede que w ∈ L, pois esta poderá pertencer a uma linguagem L
(j)
com j = k.
Como uma extensão dessa definição, dizemos que (s, j) é um fator de (w, k) se s ≺
t
w e j ≡ k + t
mod T . Se s ≺
0
w então (s, k) é um prefixo de (w, k) (prefixo própriose |s| < |w|). Quando s ≺
t
w
e k + t + |s| ≡ k + |w| mod T então (s, k + t mod T ) é um sufixo de (w, k) (sufixo próprio se
t > 0 ). Na próxima definição estenderemos o conceito de contexto à direita de uma palavra w ∈ A
∗
para um elemento (w, k).
Definição 4.3. O contexto à direita de w ∈ L associado a uma fase k é F(w, k) = {s| ws ∈ L
(k)
}.
O complemento do contexto à direita em relação a linguagem L é dado por F
′
(w, k) = L\F(w, k),
ou F
′
(w, k) = {s ∈ L| ws /∈ L
(k)
}.
56
Exemplo 4.2. Como exemplo do contexto à direita de uma palavra associado a uma fase, consi-
deremos o conjunto O e período do Exemplo 4.1. Paraw = 1, temos que 11 ∈ F(1, 0) e 01 ∈ F(1, 1),
no entanto, 01 /∈ F(1, 0) e 11 /∈ F(1, 1).
Caso (w, k) não seja definido, então para todo s ∈ L teremos que ws /∈ L
(k)
. Portanto, para todo
w /∈ L
(k)
, segue da Definição 4.3 que F(w, k) = ∅ , implicando que F
′
(w, k) = L. Prosseguindo
com o paralelismo com relação aos conceitos apresentados no Capítulo 3, a próxima definição apre-
senta o
conjunto das restrições
para o caso periódico.
Definição 4.4. Seja (w, k) ∈ L × {0, . . . , T − 1}. Um conjunto C(w, k) ⊆ L × N ∪ {0}, chamado
conjunto das restrições de (w, k), satisfaz as propriedades:
a. Seja (u, j) ∈ C(w, k), para todo s ∈ L se u ≺
j
s então ws /∈ L
(k)
;
b. Seja s ∈ L e ws /∈ L
(k)
, então existe (u, j) ∈ C(w, k) tal que u ≺
j
s.
Quando w /∈ L
(k)
, definimos C(w, k) = (ε, 0).
Definimos a seguir um operador que quando aplicado ao conjunto das restrições de um elemento
(w, k) determina o contexto à direita da palavra w, o que será demonstrado na proposição seguinte.
Definição 4.5. Seja C(w, k) o conjunto das restrições de (w, k) ∈ L × { 0, . . . , T −1}. Se w ∈ L
(k)
então [C(w, k)] = {s ∈ L| ∃(u, j) ∈ C(w, k) tal que u ≺
j
s}, caso contrário [C(w, k)] = L.
Proposição 4.1. Seja L a linguagem de um PFT. Se w ∈ L então [C(w, k)] = F
′
(w, k). Portanto,
[C(w, k)] = [C(w
′
, j)] se, e somente se, F(w, k) = F(w
′
, j).
Demonstração: Se w /∈ L
(k)
então ws /∈ L
(k)
para todo s ∈ L, logo F
′
(w, k) = L. Da
Definição 4.5, se w /∈ L
(k)
então [C(w, k)] = L. A seguir consideramos que w ∈ L.
Se s ∈ F
′
(w, k) então ws /∈ L
(k)
, logo da Definição 4.4-b existe (u, j) ∈ C(w, k) tal que
u ≺
j
s e, portanto, s ∈ [C(w, k)], conseqüentemente F
′
(w, k) ⊆ [C(w, k)]. De modo reverso, se
s ∈ [C(w, k)], então pela Definição 4.5 existe (u, j) ∈ C(w, k) tal que u ≺
j
s. Da Definição 4.4-a
ws /∈ L
(k)
e, portanto, s ∈ F
′
(w, k), logo [C(w, k)] ⊆ F
′
(w, k).
Se [C(w, k)] = [C(w
′
, j)] então F
′
(w, k) = F
′
(w
′
, j), logo da Definição 4.3 concluímos que
F(w, k) = F(w
′
, j). Se agora considerarmos que F(w, k) = F(w
′
, j), então F
′
(w, k) = F
′
(w
′
, j) e,
portanto, [C(w, k)] = [C(w
′
, j)].
57
4.2 Determinação de palavras com mesmo contexto à direita
Vimos no Capítulo 3 como determinar palavras de mesmo contexto à direita empregando o con-
junto O do SFT. Para este caso, as restrições independem da coordenada, implicando que uma se-
qüência com um fator em O não pertence a F(w) para qualquer w em B(X
O
). No caso de um PFT
as restrições estão associadas a fases, portanto, geralmente dependem da fase escolhida como refe-
rência, e.g., se a partir da fase 0 qualquer palavra w com v ≺
i
w e v ∈ O
(i)
não pode ocorrer, em
relação a fase j as palavras u com v ≺
(i−j mod T )
u não poderão ocorrer. Logo, com relação a fase
j o conjunto das restrições considerado é {(v, i − j mod T )| (v, i) ∈ O}.
A dependência das restrições com a fase torna a definição do contexto à direita de uma palavra
w dependente não só desta e do conjunto O, como também da fase. Assim, para representarmos as
restrições de uma palavra w com relação a uma fase k, iremos dividir C(w, k) em dois subconjuntos,
enquanto um depende dos sufixos de w e da fase k, o outro depende do comprimento de w e da fase
k.
Definição 4.6. Seja A ⊆ L × {0 . . . T − 1}. Representamos a expansão do conjunto A para um
período T por < A >= {(s, j)| (s, j mod T ) = (s, i) para todo (s, i) ∈ A e j ≥ 0}.
Definição 4.7. Seja w uma palavra da linguagem de um PFT. Se w ∈ L
(k)
então C
d
O
(w, k) =
{(s, 0)| s ∈ L
(k+|w| mod T )
e ∃p ∈ S(w)\{ε} para o qual ps ∈ O
(k+|w|−|p| mod T )
} e C
i
O
(w, k)
= {(s, j)| (s, j) = (s, i − k − |w| mod T ) para algum (s, i) ∈ O}. Se w /∈ L
(k)
definimos
C
d
O
(w, k) = C
i
O
(w, k) = (ε, 0). Definimos C
O
(w, k) = C
d
O
(w, k)∪ < C
i
O
(w, k) > como o con-
junto de todas as restrições indexadas de (w, k).
Lema 4.2. Se C
O
(w, k) = C
O
(u, j) então C
d
O
(w, k) = C
d
O
(u, j) e C
i
O
(w, k) = C
i
O
(u, j).
Demonstração: Suponhaque existe (s, 0) ∈ C
d
O
(w, k), tal que (s, 0) ∈ C
i
O
(u, j). Como (s, 0) ∈
C
d
O
(w, k), então ps ∈ O
(k+|w|−|p| mod T )
, onde p ∈ S(w)\{ε}. Assim, (ps, −|p| mod T ) ∈
C
i
O
(w, k), portanto, temos que (ps, −|p| mod T ) ∈ C
i
O
(u, j) e por suposição que (s, 0) ∈ C
i
O
(u, j),
por conseqüência s ∈ O
(|u|+j mod T )
é um fator de ps ∈ O
(|u|+j−|p| mod T )
, mas, como todo fator
próprio de (ps, |u| + j − |p| mod T ) pertence a linguagem, isto é uma contradição.
De forma análoga, se supusermos que (s, 0) ∈ C
d
O
(u, j) e (s, 0) ∈ C
i
O
(w, k), concluiremos que
isto é uma contradição. Portanto, se C
O
(w, k) = C
O
(u, j), então (s, 0) ∈ C
d
O
(w, k) se, e somente se
(s, 0) ∈ C
d
O
(u, j).
Exemplo 4.3. Considere um PFT dado pelo conjunto O = { (11, 0), (1, 2), (01, 3)} e com período
58
T = 5. Então para (w, k) = (1, 0) teremos C
d
O
(1, 0) = {(1, 0)} e C
i
O
(1, 0) = {(1, 1), (01, 2),
(11, 4)}, para (w, k) = (0, 3) teremos C
d
O
(0, 3) = {(1, 0)} e C
i
O
(0, 3) = {(11, 1), (1, 3), (01, 4)}.
Observamos que [C
d
O
(1, 0)] = [C
d
O
(0, 3)], contudo a seqüência 001011 ∈ [C
O
(0, 1)] pois 11 ≺
4
001011, no entanto, 001011 /∈ [C
O
(0, 3)], pois não há fatores do conjunto < C
i
O
(0, 3) > em 001011.
Portanto, [C
O
(1, 0)] = [C
O
(0, 3)].
Na próxima proposição demonstraremos que C
O
(w, k) é um possívelconjunto das restrições para
uma palavra w ∈ L
(k)
.
Proposição 4.3. Seja w ∈ L
(k)
, em que L é a linguagem de X
{O,T }
, então [C(w, k)] = [C
O
(w, k)].
Demonstração: Para todo s ∈ [C
O
(w, k)] há um fator u ≺
j
s tal que (u, j) ∈ C
d
O
(w, k)∪
< C
i
O
(w, k) >. Se (u, j) ∈ < C
i
O
(w, k) > então (u, j + k + |w| mod T ) ∈ O e portanto ws /∈ L
(k)
.
No entanto, se (u, j) ∈ C
d
O
(w, k) então existe p ∈ S(w)\{ε}tal que pu ∈ O
(k+|w|−|p| mod T )
, como
pu ≺
|w|−|p|
ws então ws /∈ L
(k)
. Logo, [C
O
(w, k)] ⊆ [C(w, k)].
Se considerarmos que s ∈ [C(w, k)], decorre da Definição 4.5 que existe (u, j) ∈ C(w, k) tal
que u ≺
j
s. Da Definição 4.4.a temos que ws /∈ L
(k)
, assim existe v ∈ O
(k+t mod T )
tal que
v ≺
t
ws. No entanto v ⊀
t
w (pois w ∈ L
(k)
). Caso t ≥ |w|, então s ∈ [< C
i
O
(w, k) >] pois
(v, t − |w| mod T ) ∈ C
i
O
(w, k). Se t < |w|, então existe p ∈ S(w)\{ε} e q ∈ P(s)\{ε} tal que
v = pq ∈ O
(k+|w|−|p| mod T )
, logo s ∈ [C
d
O
(w, k)]. Concluímos que [C(w, k)] ⊆ [C
O
(w, k)], e o
resultado segue.
Como no caso de um SFT há uma forma recursiva para calcularmos os conjuntos C
d
O
(w, k). Para
uma palavra não nula w ∈ L
(k)
, w = a
0
a
2
. . . a
n−1
, o cálculo é realizado do prefíxo de menor com-
primento (a
0
) para o de maior comprimento a
0
. . . a
n−1
, empregando a definição R(C
d
O
(w, k)) =
{s | (s, 0) ∈ C
d
O
(w)}, temos que:
R(C
d
O
(a
0
, k)) = a
−1
0
O
(k)
,
R(C
d
O
(a
0
a
1
, k)) = a
−1
1
R(C
d
O
(a
0
, k)) ∪ a
−1
1
O
(k+1 mod T )
,
.
.
.
R(C
d
O
(a
0
. . . a
n−1
, k)) = a
−1
n−1
R(C
d
O
(a
0
. . . a
n−2
, k)) ∪ a
−1
n−1
O
(k+n−1 mod T )
.
(4.1)
A prova desta relação é apresentada à seguir pelo desenvolvimento do conjunto R(C
d
O
(w, k)), a
partir da descrição do conjunto C
d
O
(w, k) dada na Definição 4.7.
59
R(C
d
O
(a
0
. . . a
n−1
, k)) =
n
i=1
(a
n−i
. . . a
n−1
)
−1
O
(k+n−i mod T )
=
n
i=2
(a
n−i
. . . a
n−1
)
−1
O
(k+n−i mod T )
∪a
−1
n−1
O
(k+n−1 mod T )
=
n
i=2
a
−1
n−1
(a
n−i
. . . a
n−2
)
−1
O
(k+n−i mod T )
∪a
−1
n−1
O
(k+n−1 mod T )
= a
−1
n−1
n
i=2
(a
n−i
. . . a
n−2
)
−1
O
(k+n−i mod T )
∪a
−1
n−1
O
(k+n−1 mod T )
= a
−1
n−1
R(C
d
O
(a
0
. . . a
n−2
, k)) ∪ a
−1
n−1
O
(k+n−1 mod T )
.
Exemplo 4.4. Seja T = 3 o período do Shannon cover de um PFT. Dados os conjuntos O
(0)
=
{1111, 1011 }, O
(1)
= ∅ e O
(2)
= {111, 1101}, segue o cálculo dos conjuntos R(C
d
O
(w, k)) para
(111, 0) e (110, 2):
R(C
d
O
(1, 0)) = 1
−1
O
(0)
= {111, 011 },
R(C
d
O
(11, 0)) = 1
−1
R(C
d
O
(1, 0)) ∪ 1
−1
O
(1)
= {11},
R(C
d
O
(111, 0)) = 1
−1
R(C
d
O
(11, 0)) ∪ 1
−1
O
(2)
= {1, 11, 101},
R(C
d
O
(1, 2)) = 1
−1
O
(2)
= {11, 101} ,
R(C
d
O
(11, 2)) = 1
−1
R(C
d
O
(1, 2)) ∪ 1
−1
O
(0)
= {1, 01, 111, 011},
R(C
d
O
(110, 2)) = 1
−1
R(C
d
O
(11, 2)) ∪ 1
−1
O
(1)
= {1, 11}.
O Lema 4.4 nos permite concluir, para um PFT irredutível de linguagem L, que, para qualquer
w ∈ L
(k)
e (v, n) ∈ C
i
O
(w, k) existe uma palavra uv em [C
O
(w, k)] que só possui v ≺
|u|
uv como
fator proibido, onde |u| ≡ n mod T . Portanto, quando consideramos a linguagem indexada L
(k)
, o
único fator proibido de (wuv, k) é (v, |wu|+ k mod T ), onde (|wu|+ k) −(k + |w|) ≡ n mod T .
Assim, qualquer elemento em C
i
O
(w, k) é uma restrição não dispensável do conjunto C
O
(w, k), ou
seja, retirá-la do conjunto C
O
(w, k) implica que a Proposição 4.1 não seria verificada.
Lema 4.4. Seja X
{O,T }
um PFT irredutível. Para qualquer v = pa ∈ A
∗
, a ∈ A, v ∈ O
(n)
se, e
somente se,
(i) ∀s ≺
ℓ
v, s ∈ L
(n+ℓ mod T )
;
(ii) wuv /∈ L
(k)
para todo wup ∈ L
(k)
em que k + |wu| ≡ n mod T , qualquer k ∈
{0, . . . , T − 1} e w ∈ L
(k)
.
Demonstração: Chamaremos de G o Shannon cover de X
{O,T }
(a irredutibilidade de X
{O,T }
garante sua existência), T = per( A
G
) e D
0
, . . . , D
T −1
as classes periódicas de G. A implicação
60
direta segue da definição dos elementos em O para afirmação (i). Para afirmação (ii), seja k ∈
{0, . . . , T − 1} e w ∈ L
(k)
, portanto, existe pelo menos um caminho ξ em G tal que L(ξ) = w,
i(ξ) ∈ D
k
e t(ξ) ∈ D
(k+|w| mod T )
. Tomemos um caminho π em G para o qual L(π) = p e
i(π) ∈ D
n
, como p ∈ L
(n)
então este caminho existe. Já que G é irredutível, existe um caminho φ
em G para o qual i(φ) = t(ξ) e t(φ) = i(π), logo temos que wL(φ)p ∈ L
(k)
e wL(φ)v /∈ L
(k)
, uma
vez que o vértice inicial do caminho com rótulo v em wL(φ)v pertence à classe D
n
. O que concluí
a prova direta, pois, w é uma palavra qualquer em L
(k)
e π é qualquer caminho, tal que, L(π) = p e
i(π) ∈ D
n
.
Da afirmação (i), temos que v
[0,|v|−2]
∈ L
(n)
e v
[1,|v|−1]
∈ L
(n+1 mod T )
. Da afirmação (ii),
temos que v /∈ L
(n)
. Portanto, peladefiniçãodos elementosdoconjunto O, concluímos que v ∈ O
(n)
.
Os conjuntos C
O
(w, k) podem ser reduzidos pela eliminação de elementos (s, k) ∈ C
O
(w, k)
que possuem prefixos próprios em C
O
(w, k), o que é justificado observando-se que para todo prefixo
(s
′
, k) de (s, k) temos que [(s, k)] ⊂ [(s
′
, k)], portanto concluímos que [C
O
(w, k)] = [C
O
(w, k)\
{(s, k)}]. Escreveremos
˜
C
O
(w, k) para indicar que eliminações deste tipo não podem ser realizadas
no conjunto C
O
(w, k). Observamos que um elemento (s, j) ∈ C
O
(w, k) só poderá ter um fa-
tor próprio (s
′
, i) ∈ C
O
(w, k) se (s
′
, i) ∈ C
d
O
(w, k), ou seja i = j = 0, caso contrário s
′
∈
O
(i+k+|w| mod T )
será um fator próprio de s ∈ O
(j+k+|w| mod T )
, o que contradiz a definição dos
elementos de O.
Exemplo 4.5. Os conjuntos R(C
d
O
(w, k)) calculadosno Exemplo4.4 possuemos seguintes conjuntos
R(
˜
C
d
O
(w, k)) correspondentes:
R(
˜
C
d
O
(1, 0)) = {111 , 011},
R(
˜
C
d
O
(11, 0)) = {11},
R(
˜
C
d
O
(111, 0)) = {1},
R(
˜
C
d
O
(1, 2)) = {11, 101},
R(
˜
C
d
O
(11, 2)) = {1, 01, 011},
R(
˜
C
d
O
(110, 2)) = {1}.
No próximo teorema mostraremos que elementos em L ×{0, . . . , T −1} com o mesmo contexto
à direita possuem conjuntos
˜
C
O
(w, k) iguais, dado que o PFT é irredutível.
Teorema 4.5. Seja w ∈ L
(k)
e w
′
∈ L
(j)
, então
˜
C
O
(w, k) =
˜
C
O
(w
′
, j) se, e somente se, F(w, k) =
F(w
′
, j).
61
Demonstração: Se
˜
C
O
(w, k) =
˜
C
O
(w
′
, j) então [
˜
C
O
(w, k)] = [
˜
C
O
(w
′
, j)], o que das Proposi-
ções 4.1 e 4.3 implica que F(w, k) = F(w
′
, j).
Para provarmos a recíproca, inicialmente demonstraremos que se F(w, k) = F(w
′
, j) então
˜
C
i
O
(w, k) =
˜
C
i
O
(w
′
, j) e usaremos isto para provar que
˜
C
d
O
(w, k) =
˜
C
d
O
(w
′
, j). Seja (v, n) ∈
˜
C
i
O
(w, k). Supondo que v = pa, a ∈ A, para todo up ∈ F(w, k), tal que |u| ≡ n mod T ,
temos que upa = uv /∈ F(w, k), logo a igualdade F(w, k) = F(w
′
, j) implica que uv /∈ F(w
′
, j).
Da definição dos elementos do conjunto
˜
C
i
O
(w, k), para todo fator próprio s ≺
ℓ
v de v existe u
′
,
tal que |u
′
| ≡ n + ℓ mod T , satisfazendo u
′
s ∈ F(w, k) e, portanto, u
′
s ∈ F(w
′
, j), implicando
que s ∈ L
(n+j+|w
′
|+ℓ mod T )
. Assim, a partir do Lema 4.4 temos que v ∈ O
(n+j+|w
′
| mod T )
,
logo (v, n) ∈
˜
C
i
O
(w
′
, j), de onde concluímos que
˜
C
i
O
(w, k) ⊆
˜
C
i
O
(w
′
, j). Supondo que (v, n) ∈
˜
C
i
O
(w
′
, j), podemos concluir de forma semelhante que
˜
C
i
O
(w
′
, j) ⊆
˜
C
i
O
(w, k).
Dadas as igualdadesF(w, k) = F(w
′
, j) e
˜
C
i
O
(w, k) =
˜
C
i
O
(w
′
, j), demonstraremosquea hipótese
˜
C
d
O
(w, k) =
˜
C
d
O
(w
′
, j) gera uma contradição. Assim, seja
˜
C
d
O
(w, k) =
˜
C
d
O
(w
′
, j) e s um dos elemen-
tos entre os de menor comprimento em {u| (u, 0) ∈ (
˜
C
d
O
(w, k)\
˜
C
d
O
(w
′
, j))∪(
˜
C
d
O
(w
′
, j)\
˜
C
d
O
(w, k))}.
Iremos supor, sem perda de generalidade, que (s, 0) ∈
˜
C
d
O
(w, k) e portanto que s ∈ [
˜
C
O
(w, k)].
Existe v = ps tal que v ∈ O
(k+|w|−|p| mod T )
e p ∈ S(w)\{ε}, portanto, se considerarmos que
s ∈ [<
˜
C
i
O
(w
′
, j) >] = [<
˜
C
i
O
(w, k) >], então existe s
′
≺
|p+t|
v para algum (s
′
, t) ∈
˜
C
i
O
(w, k), isto
implica que s
′
∈ O
(k+|w|+t mod T )
é um fator de v ∈ O
(k+|w|−|p| mod T )
, o que é uma contradição.
Logo, podemos afirmar que s /∈ [<
˜
C
i
O
(w
′
, j) >]. Nos limitando aos elementos de
˜
C
d
O
(w
′
, j), temos
três casos a considerar (i) s /∈ [{(u, 0)| ( u, 0) ∈
˜
C
d
O
(w
′
, j) e |u| > |s|}], uma vez que u ⊀
0
s para
qualquer u tal que |u| > |s|; (ii) s /∈ [{(u, 0) | (u, 0) ∈
˜
C
d
O
(w
′
, j) e |u| = |s|}], já que por hipótese
(s, 0) /∈
˜
C
d
O
(w
′
, j); (iii) s /∈ [{(u, 0)| (u, 0) ∈
˜
C
d
O
(w
′
, j) e |u| < |s|}], pois da definição da palavra s,
temos que {(u, 0) ∈
˜
C
d
O
(w, k)| |u| < |s|} = {(u, 0) ∈
˜
C
d
O
(w
′
, j)| |u| < |s|} implicando que não há
(v, 0) ∈
˜
C
d
O
(w
′
, j) tal que v ⊀
0
s. Logo, s /∈ [
˜
C
O
(w
′
, j)] e, portanto, da Proposição 4.1, concluímos
que F(w, k) = F(w
′
, j), o que contradiz a hipótese de (w, k) e (w
′
, j) terem o mesmo contexto à
direita.
4.3 Construção de uma apresentação reduzida
Nesta seção proporemos um método para gerar uma apresentação G = (V, E, λ) de um PFT a
partir de um conjunto mínimo periódico de palavras proibidas O. Começamos por definir o conjunto
V, que tem como elementos as classes de equivalência provenientes da partição de W ∪ O, sendo W
62
definido a seguir.
Definição 4.8. Dado o conjunto O associado a um PFT, definimos o conjunto W =
T −1
k=0
W
(k)
,
onde:
W
(k)
=
{(u, k)| u ∈ P(wA
−1
), ∀ (w, k) ∈ O
(k)
} , se O
(k)
= ∅,
{(ε, k)} , c.c. .
A partição do conjunto W ∪ O é determinada pela relação de equivalência: (w, k) ∼ (u, j) se,
e somente se,
˜
C
O
(w, k) =
˜
C
O
(u, j). Portanto, (w, k) ∼ (u, j) se, e somente se, F(w, k) = F(u, j),
justificado pelo Teorema 4.5. Decorre dessa relação que o conjunto O forma uma classe, já que para
todo (v, k) ∈ O e x ∈ L temos que vx /∈ L
(k)
.
A partir deum conjuntoV, iremos determinaro conjunto de ramos e seus rótulos. SejaC
i
, C
j
∈ V
e C
i
= O, criaremos um ramo de C
i
para C
j
com rótulo a, se para algum dos (w, k) ∈ C
i
o mais
longo sufixo de (wa, k) em W ∪ O pertence a C
j
. Descrevemos com maior precisão o método de
determinação dos ramos na próxima definição.
Definição 4.9. Seja C
i
∈ V\{O} e (w, k) ∈ C
i
. A relação δ : V\{O} × A ∪ {ε} → V é definida
como
δ(C
i
, a) = {Q| (v, k + r mod T ) ∈ Q, a ∈ A ∪{ε} e v = wa
[r,|wa|−1]
é o mais
longo sufixo de (wa, k) tal que (v, k + r mod T ) ∈ W ∪ O}.
A partir da Definição 4.9, observamos que não há ramos partindo da classe O. Tendo definido o
conjunto de vértices, os ramos e seus rótulos, seguiremos demonstrando que G é uma apresentação
determinística e reduzida de um PFT irredutível especificado por um conjunto mínimo periódico de
palavras proibidas O e período T . Nos próximos dois lemas apresentaremos algumas propriedades
dos conjuntos
˜
C
O
(w, k) que nos permitirão concluir que G é um grafo determinístico.
Lema 4.6. Para todo w ∈ L
(k)
e u ∈ L
(j)
, se
˜
C
O
(w, k) =
˜
C
O
(u, j) então
˜
C
O
(wa, k) =
˜
C
O
(ua, j).
Demonstração: Pelo Teorema 4.5,
˜
C
O
(w, k) =
˜
C
O
(u, j) se, e somente se, F(w, k) = F(u, j).
Logo waz ∈ L
(k)
se, e somente se, waz ∈ L
(j)
, portanto F(wa, k) = F(ua, j), ou
˜
C
O
(wa, k) =
˜
C
O
(ua, j).
Lema 4.7. Seja w ∈ L
(k)
. Se (v, ℓ) é o mais longo sufixo de (w, k) em W, então
˜
C
O
(w, k) =
˜
C
O
(v, ℓ).
63
Demonstração: Supondo que v = w
[r,|w|−1]
, então o comprimento de v é |v| = |w| − r. Logo,
a partir da equação ℓ ≡ k + r mod T , temos que |v| + ℓ ≡ |w| − r + k + r ≡ |w| + k mod T ,
portanto C
i
O
(w, k) = C
i
O
(v, ℓ).
Observemos que C
d
O
(v, ℓ) ⊆ C
d
O
(w, k), pois (v, ℓ) é uma sufixo de (w, k). Para a demonstração
da inclusão reversa, consideremos que (s, 0) ∈
˜
C
d
O
(w, k), logo existe p = w
[i,|w|−1]
tal que ps ∈
O
(k+i mod T )
, portanto (p, k + i mod T ) é um sufixo de (w, k) em W. Uma vez que (v, ℓ) é o mais
longo sufixo de (w, k) em W, então (p, k + i mod T ) também é um sufixo de (v, ℓ), o que implica
que (s, 0) ∈ C
d
O
(v, ℓ). Se (s
′
, 0) é um prefixo de (s, 0) contido em C
d
O
(v, ℓ), então (s
′
, 0) ∈ C
d
O
(w, k)
implicando que (s, 0) /∈
˜
C
d
O
(w, k), o que é uma contradição. Logo, temos que
˜
C
d
O
(w, k) ⊆
˜
C
d
O
(v, ℓ).
Concluímos que
˜
C
O
(w, k) =
˜
C
O
(v, ℓ).
Proposição 4.8. O grafo G é determinístico.
Demonstração: Para C
i
= O e (w, k), (u, j) ∈ C
i
, consideremos (w
′
, k
′
) e (u
′
, j
′
) os mais lon-
gos sufixos de (wa, k) e (ua, j) em W ∪ O, respectivamente. Do Lema 4.6
˜
C
O
(wa, k) =
˜
C
O
(ua, j),
então para (w
′
, k
′
) ∈ C
t
e (u
′
, j
′
) ∈ C
ℓ
temos que C
t
= C
ℓ
, pois do Lema 4.7 decorre a igualdade
˜
C
O
(w
′
, k
′
) =
˜
C
O
(u
′
, j
′
).
Como apresentada na Definição 4.9 a relação δ é uma função, a Proposição 4.8 nos permite
concluir que esta função é bem definida.
Seja C
i
= O, uma palavra u é dita definida por C
i
se, e somente se, existe um caminho partindo
de C
i
com rótulo u. O que nos leva a uma natural modificação do domínio da função δ para grafos
determinísticos, de V × A ∪ {ε} para V × A
∗
. Para qualquer C
i
∈ V\{O} e u ∈ A
∗
, caso o estado
O seja alcaçado a partir de C
i
por um prefixo próprio de u, então u não é definida por C
i
, pois O não
possui ramos partindo deste; caso contrário, δ(C
i
, u) é o estado alcançado a partir de C
i
por u.
No próximo teorema empregaremos este conceito para concluir que G é uma apresentação de
X
{O,T }
. Por G ser determinístico, para qualquer palavra u definida por um vértice C
i
há um único
caminho π em G tal que λ(π) = u e i(π) = C
i
, portanto, se δ(C
i
, u) = O então u /∈ F(C
i
), pois
não há ramos partindo de O e portanto este não pertence a componente essencial de G.
Lema 4.9. Seja (w, k) ∈ C
i
e C
i
= O. Se u é definido por C
i
, então o mais longo sufixo de (wu, k)
contido em W ∪ O pertence a δ(C
i
, u).
Demonstração: Realizaremos uma prova por indução no comprimento de u. Inicialmente, se
u = ε então a afirmação é satisfeita. Portanto, iremos supor que o lema é satisfeito para algum
64
|u| = r > 0. Seja x = ua uma palavra definida por C
i
, a ∈ A, portanto, existe um ramo partindo do
vértice δ(C
i
, u) com rótulo a para o vértice δ(δ(C
i
, u), a). Da hipótese indutiva o mais longo sufixo
de (wu, k) em W ∪ O pertence a δ(C
i
, u) e δ(C
i
, u) ⊆ W.
Seja (u
′
, k
′
) ∈ δ(C
i
, u) o mais longo sufixo de (wu, k) em W e seja v = u
′
a
[t,|u
′
a|−1]
, tal
que (v, k
′
+ t mod T ), o mais longo sufixo de (u
′
a, k
′
) em W ∪ O. Consideremos que v
′
a =
wua
[t
′
,|ua|−1]
seja um sufixo de (wua, k) em W ∪ O. Então (v
′
, t
′
+ k mod T ) é um sufixo de
(wu, k) em W ∪O, portanto (v
′
, t
′
+ k mod T ) é um sufixo de (u
′
, k
′
), implicando que (v
′
a, t
′
+ k
mod T ) é um sufixo de (u
′
a, k
′
). Assim, concluímos que (v, k
′
+ t mod T ) é o mais longo sufixo
de (wua, k) em W ∪ O.
Teorema 4.10. A componente essencial de G é uma apresentação reduzida do PFT.
Demonstração: Seja x uma palavra não nula e C
i
∈ V\{O}, tal que x ∈ F(C
i
), (w, k) ∈ C
i
e δ(C
i
, x) = O. Considerando que (wx, k) possui fatores em O, seja v = wx
[t,|v|+t−1]
o fa-
tor de (wx, k) em O que inicia no menor coeficiente t de wx. Então, do Lema 4.9 temos que
δ(C
i
, wx
[0,t+|v|−1]
) = O, logo x /∈ F(C
i
), o que é uma contradição. Isso implica que F(C
i
) ⊆
F(w, k). Reciprocamente, seja x ∈ F(w, k), então (wx, k) não possui fatores em O. Se (w, k) ∈ C
i
,
então, para todo prefixo x
′
de x temos que δ(C
i
, x
′
) = O, logo x ∈ F(C
i
). Isso implica que
F(w, k) ⊆ F(C
i
). Assim, concluímos que F(C
i
) = F(w, k) para qualquer (w, k) ∈ C
i
.
Dada uma palavra w ∈ L
(k)
e sendo (w
′
, k
′
) seu mais longo sufixo em W (como w ∈ L
(k)
,
(w, k) não possui fatores em O), a partir do Lema 4.7 e do Teorema 4.5, concluímos que F(w, k) =
F(w
′
, k
′
) = F(C
i
), tal que (w
′
, k
′
) ∈ C
i
. Uma vez que F(ε, k) = L
(k)
e para qualquerpalavra x ∈ L
temos que x ∈ L
(j)
para alguma fase j ∈ {0, . . . , T − 1}, concluímos que
C
i
∈V\{O}
F(C
i
) = L.
Portanto, o subgrafo de G com conjunto de vértices V\{O} é uma apresentação do PFT, logo, a
componente essencial de G também é uma apresentação do PFT. Para demonstração que G é uma
apresentação reduzida, sejam C
i
, C
ℓ
∈ V\{O} tal que F(C
i
) = F(C
ℓ
), se (w, k) ∈ C
i
e (u, j) ∈
C
ℓ
então, do Teorema 4.5, temos que
˜
C
O
(w, k) =
˜
C
O
(u, j), logo C
i
= C
ℓ
, o que implica que a
componente essencial é reduzida.
4.4 Sistemas restritos com posições irrestritas
Sistemas restritos com posições irrestritas
são definidos em [2] como: Seja X um sistema sim-
bólico fechado, T um período e U ⊆ {0, . . . , T − 1} um conjunto de
posições irrestritas
. Para
65
qualquer seqüência finita x da linguagem (respectivamente, infinita, bi-infinita), uma U-permutação
de x é uma seqüência finita y (respectivamente, infinita, bi-infinita), tal que y
i
= x
i
sempre que i
mod T /∈ U. Se A é o alfabeto binário {0, 1}, uma U-permutação é obtida pela inversão ou não dos
dígitos nas posições irrestritas. O conjunto de todas as U-permutações das palavras em um conjunto
S é chamado U-fechamento de S.
Define-se por X
U,T
o conjunto de todas as seqüências x de X (respectivamente, infinita, bi-
infinita) para as quais:
⊲ Toda U-permutação de x pertence a X;
⊲ x
i
= 1 para toda posição i para a qual i mod T ∈ U.
As posições irrestritas são forçadas a serem 1 para estabelecer um líder em cada classe de U -
permutações. O importante é que os valores nas posições irrestritas possam ser alterados indepen-
dentemente sem com isto violar a restrição de X. Os deslocamentos das seqüências em X
U,T
podem
não estar em X
U,T
(i.e, X
U,T
não é um sistema simbólico fechado). O conjunto de todos os desloca-
mentos das seqüências em X
U,T
é denotado por X
σ
U,T
. O conjunto de todas as seqüências bi-infinitas
e deslocadas decorrentes do conjunto X
σ
U,T
é denotado por
X
σ
U,T
. A conexão entre os conjuntos
X
σ
U,T
, X
σ
U,T
e os PFT é dado na próxima proposição.
Proposição 4.11. [3, Proposição 1] Seja X um SFT, T um período e U um conjunto de posições
irrestritas. Os sistemas simbólicos fechados
X
σ
U,T
e X
σ
U,T
são PFT.
Este resultado é provado construtivamente pela definição dos conjuntos proibidos associados, e
pela demonstraçãode que estesrealmente geram os sistemassimbólicos fechados. Dado um conjunto
U ⊆ {0, . . . , T − 1} e sendo k um inteiro, o conjunto U + k é definido como {i + k mod T | i ∈
U}. Seja X = X
F
, então
X
σ
U,T
= X
G
′
,T
tal que G
′(k)
é o (U − k)-fechamento de F, em que
k ∈ {0, . . . , T − 1}; X
σ
U,T
= X
G,T
tal que G
(k)
= G
′(k)
se k ∈ U e G
(k)
= {0} ∪ G
′(k)
se
k ∈ {0, . . . , T − 1}\U.
Exemplo 4.6. Considerando a restrição MTR(3), o conjunto proibido associado é F = {1111},
portanto, para um período T = 3 e conjunto de posições irrestritas U = {1}, temos que G
′(0)
=
{1111, 1011 }, G
′(1)
= {1111, 0111} e G
′(2)
= {1111, 1101}. O conjunto O associado é o apresen-
tado no Exemplo 4.4. Calculando os conjuntos
˜
C
d
O
(w, k) restantes, temos que
˜
C
d
O
(10, 0) = {(11, 0)}
e
˜
C
d
O
(101, 0) = {(1, 0)}. Os conjuntos
˜
C
i
O
(w, k) associados a cada elemento de W são apresentados
na Tabela 4.6. Assim, temos as seguintes classes de equivalência C
1
= {(ε, 0)}, C
2
= {(ε, 1)},
C
3
= {(ε, 2)}, C
4
= {(1, 0)}, C
5
= {(11, 0), (10, 0)} , C
6
= {(111, 0), (101, 0)}, C
7
= {(1, 2)},
66
C
8
= {(11, 2)} e C
9
= {(110, 2)}. O grafo associado é apresentado na Figura 4.3. Os conjuntos
˜
C
d
O
(w, k) e
˜
C
i
O
(w, k) dos elementos de W, as classes as quais esses pertencem e o cálculo da função
de transição são apresentados na Tabela 4.6. Da Proposição 4.8 e da Proposição 4.10 sabemos que o
grafo da Figura 4.3 apresenta o PFT e é reduzido e determinístico. Verificamos que este também é
irredutível, portanto, o grafo é o Shannon cover do PFT que satisfaz a restrição MTR(3), com T = 3
e U = {1}.
Para exemplificarmos o cálculo da função δ, consideremos a classe C
5
. Da Tabela 4.6, temos
que C
5
= {(10, 0), (11, 0)}, usando (10, 0) para determinarmos δ(C
5
, 0) e δ(C
5
, 1), observe que
os máximos prefixos de (100, 0) e (10 1, 0) em W são (ε, 0) e (101, 0), respectivamente, portanto, a
partir de (10, 0) obtemos que δ(C
5
, 0) = C
1
e δ(C
5
, 1) = C
6
. Se empregarmos (11, 0), os máximos
prefixos de (110, 0) e (111, 0) em W são (ε, 0) e (101, 0), respectivamente,o que conduzaos mesmos
resultados obtidos quando empregamos (10, 0).
C
1
C
2
C
3
C
6
C
9
C
7
C
8
C
4
C
5
0
1
1
0
1
1
0
0
0
0
0
10
1
0
Figura 4.3: Apresentação de um PFT satisfazendo a restrição MTR(3) com T = 3 e U = {1}.
67
Tabela 4.1: Cálculo das classes de equivalência e da função δ para o PFT do Exemplo 4.6.
(w, k) ∈ W {s | (s, 0) ∈
˜
C
d
O
(w, k)}
˜
C
i
O
(w, k)
†
Classes δ(C
i
, 0) δ(C
i
, 1)
(ε, 0) ∅ A
0
C
1
C
2
C
4
(1, 0) {111, 011} A
1
C
4
C
5
C
5
(10, 0) {11} A
2
C
5
C
1
C
6
(11, 0) {11} A
2
C
5
C
1
C
6
(101, 0) {1} A
0
C
6
C
2
O
(111, 0) {1} A
0
C
6
C
2
O
(ε, 1) ∅ A
1
C
2
C
3
C
3
(ε, 2) ∅ A
2
C
3
C
1
C
7
(1, 2) {11, 101} A
0
C
7
C
2
C
8
(11, 2) {1, 01, 011} A
1
C
8
C
9
O
(110, 2) {1} A
2
C
9
C
1
O
†
A
0
= {(1111, 0), (1011, 0), (111, 2), (1101, 2)}.
A
1
= {(111, 1), (1101, 1), (1111, 2), (1011, 2)}.
A
2
= {(111, 0), (1101, 0), (1111, 1), (1011, 1)}.
68
CAPÍTULO 5
CONCLUSÕES
Estabelecemoscomoobjetivo do trabalho a proposiçãode métodos para geraçãodeapresentações
determinísticas para SFT e PFT com númeromínimo de estadose que fossemconceitualmentedistin-
tos dos encontrados na literatura. A motivação para este trabalho reside na relação de Myhill-Nerode
e da memória finita dos sistemas simbólicos estudados. O conjunto proibido finito O com palavras
de máximo comprimento M, permite que a verificação que uma palavra da linguagem y pertencente
ao contexto à direita de outra palavra da linguagem x, seja realizada determinando-se o subconjunto
de (S(x)\{ε}) · (P(y)\{ε}) contendo todas as palavras com comprimento máximo M + 1 que não
pertencem a O. Exploramos esta propriedade para propor um algoritmo com número finito de passos
para a determinação de palavras com mesmo contexto à direita.
Com a determinação em [24] de um conjunto suficiente de palavras para gerar o grafo dos con-
textos, podemos dividir os procedimentos para geração de uma apresentação mínima, não como a
geração de uma apresentação inicial seguida de uma minimização de vértices aplicando-se os al-
goritmos de Hopcroft ou Moore, mas na determinação das classes de equivalência da relação de
Myhill-Nerode (pelo cálculo dos conjuntos das restrições) seguida da construção do grafo, ou seja,
propusemos um algoritmo que gera o conjunto de vértices do grafo determinístico mínimo de um
SFT irredutível (de maior interesse prático) antes de construir uma apresentação para o SFT. No caso
de um SFT redutível, o algoritmo gera a m-SDP que apesar de não ser isomorfa a toda apresentação
determinística com número mínimo de estados, possui o número mínimo de estados entre todas as
apresentações determinísticas.
Um PFT não é necessariamente um SFT, ou seja, em geral não possui memória finita. A memória
finita de um PFT é artificialmente gerada pela inclusão de um novo parâmetro na determinação do
conjunto proibido deste, a saber, a fase. Como as relações de equivalência não são mais definidas
sobre as palavras da linguagem, mas sobre as palavras da linguagem indexadas, a relação estabele-
cida não é mais a de Myhill-Nerode. Observamos com isto, que a determinação das restrições dos
elementos passa a depender não só dele e do conjunto proibido, mas também da fase. A partir do
conjunto de palavras indexadas proposto em [3], propusemos um procedimento para gerar uma ap-
resentação determinística e reduzida do PFT seguindo o mesmo princípio utilizado para um SFT,
ou seja, é determinado o conjunto de estados da apresentação reduzida antes de construir-se uma
apresentação para o PFT.
5.1 Trabalhos Futuros
O algoritmo de menor complexidade para gerar uma apresentação inicial de um SFT que temos
conhecimento é apresentado em [24]. A complexidade deste algoritmo é linear com o número de es-
tados. Para a obtenção da apresentação mínima, é necessário reduzir a apresentação inicial utilizando
os algoritmos de Moore ou Hopcroft. Para o caso de um SFT, no Capítulo 3 propusemos um proce-
dimento para o cálculo dos conjuntos
˜
C
r
O
(w). Este pode ser aperfeiçoado com o objetivo de obter-se
as classes de equivalência com uma complexidade de no máximo n · log n, que é a complexidade do
algoritmo de Hopcroft. Como a função de transição é calculada para um número menor de vértices
quando comparado ao algoritmo proposto em [24], teríamos um algoritmo de menor complexidade
para geração da apresentação mínima.
Para o caso de um PFT irredutível, conjecturamos que todo conjunto proibido periódico que
satisfaça as condições do conjunto O deva ter um período múltiplo do período do Shannon cover. A
obtenção deste resultado simplificaria o cálculo dos conjuntos
˜
C
O
(w, k), já que o conjunto
˜
C
i
O
(w, k)
poderia ser eliminado, pois, dois elementos (w, k), (w
′
, k
′
) com |w| + k e |w
′
| + k
′
incongruentes
(quando reduzidos pelo período do Shannon cover) teriam contextos à direita distintos.
Como o método proposto para a geração de uma apresentação de um PFT gera uma apresentação
reduzida e determinística, deve-se verificar se esta também é irredutível. Portanto, teríamos o Shan-
non cover do PFT. Pode-se estudar ainda a viabilidade de um algoritmo similar para o caso de um
PFT redutível. Por fim, como no caso não periódico, deve-se realizar a análise de complexidade do
algoritmo proposto.
70
BIBLIOGRAFIA
[1] E. R. Berlekamp, “Technology of error-correcting codes,” Proc. IEEE, vol. 68, pp. 564–593,
1980.
[2] J. C. de Souza, B. H. Marcus, R. New, and B. A. Wilson, “Constrained systems with uncon-
strained positions,” IEEE Trans. Inform. Theory, vol. 48, pp. 866–879, April 2002.
[3] M.-P. Béal, M. Crochemore, and G. Fici, “Presentations of constrained systems with uncon-
strained positions,” IEEE Trans. Inform. Theory, vol. 51, pp. 1891–1900, May 2005.
[4] B. H. Marcus, R. M. Roth, and P. H. Siegel, “Constrained systems and coding for recording
channels,” in Handbook of Coding Theory (V. S. Pless and W. Huffman, eds.), vol. 2, pp. 1635–
1764, Eds. Amsterdam:Elsevier, 1999.
[5] K. A. S. Immink, “EFMPlus: The coding format of the multimedia compact disc,” IEEE. Trans.
Consum. Electron., vol. 41, pp. 491–497, August 1995.
[6] W. Hirt, M. Hassner, and N. Heise, “IrDA-VFIr (16 Mb/s): Modulation code and system de-
sign,” IEEE Personal Communications, vol. 8, pp. 58–71, February 2001.
[7] P. Funk, “Run-length-limited codes with multiple spacing,” Trans. Magnetics, vol. 18, pp. 772–
775, 1982.
[8] B. H. Marcus and P. H. Siegel, “On codes with spectral nulls at rational sub-multiples of the
symbol frequency,” IEEE Trans. Inform. Theory, vol. 33, pp. 557–568, July 1987.
[9] M. Morse, “Recurrent geodesics on a surface of negative curvature,” Trans. Amer. Math. Soc.,
no. 22, pp. 84–110, 1921.
[10] D. Lind and B. H. Marcus, An Introduction to Symbolic Dynamics and Coding. Cambridge
University Press, 1995.
71
[11] R. L. Adler, D. Coppersmith, and M. Hassner, “Algorithms for sliding block codes: An ap-
plication of symbolic dynamics to information theory,” IEEE Trans. Inform. Theory, vol. 29,
pp. 5–22, January 1983.
[12] M.-P. Béal and D. Perrin, “Symbolic dynamics and finite automata,” in Handbook of formal
languages, vol. 2: linear modeling: background and application, pp. 463–505, Springer-Verlag
New York, 1997.
[13] N. Jonaska, “Sofic shifts with synchronizing presentations,” Theoretical Computer Science,
no. 158, pp. 81–115, 1996.
[14] N. T. Sindhushayana, “Symbolic dynamics, automata theory and the theory of coding: A com-
parative study and applications,” Master’s thesis, Cornell University, 1992.
[15] S. Eilenberg, Automata, Languages, and Machines, vol. A. Academic Press, 1974.
[16] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computa-
tion. Addison-Wesley, 1979.
[17] M. V. Lawson, Finite Automata. Chapman & Hall/CRC, 2004.
[18] R. Johnsonbaugh and W. E. Pfaffenberger, Foundations of Mathematical Analysis. Dover Pub-
lications, 2002.
[19] J. E. Hopcroft, “An (n · log n) algorithm for minimizing states in a finite automaton,” Tech.
Rep. STAN-CS-71-190, Stanford University, 1971.
[20] D. P. B. Chaves, C. Pimentel, and B. F. Uchôa-Filho, “On the shannon cover of shifts of finite
type,” in Anais do XX Simpósio Brasileiro de Telecomunicações-SBT’03,2003.
[21] D. P. B. Chaves, C. Pimentel, and B. F. Uchôa-Filho, “An iterative matrix-based procedure
for finding the shannon cover for constrained sequences,” Lecture Notes in Computer Science,
vol. 3124, pp. 88–93, 2004.
[22] K. A. S.Immink, “A survey of codesfor optical disk recording,”IEEE J.Select. AreasCommun.,
vol. 19, pp. 756–764, April 2001.
[23] B. H. Marcus, P. H. Siegel, and J. K. Wolf, “Finite-state modulation codes for data storage,”
IEEE J. Select. Areas Commun., vol. 10, pp. 5–37, January 1992.
72
[24] M. Crochemore, F. Mignosi, and A. Restrivo, “Automata and forbidden words,” Information
Processing Letters, vol. 67, pp. 111–117, 1998.
[25] B. Moision and P. H. Siegel, “Periodic-finite-type shift spaces,”in Proc.IEEE Int. Symp. Inform.
Theory, (Washington, DC), p. 65, June 2001.
[26] A. Wijngaarden and K. S. Immink, “Maximum run-length limited codes with error control
properties,” IEEE J. Select. Areas Commun., vol. 19, pp. 602–611, April 2001.
73
SOBRE O AUTOR
O autor nasceu em Recife, Pernambuco, no dia 09 de maio de 1977. For-
mado em Engenharia Elétrica (com Láurea), modalidade Eletrônica, pela Uni-
versidade Federal de Pernambuco (UFPE) em agosto de 2004.
Entre suas áreas de interesse estão teoria de códigos, processamento digital
de sinais, teoria da informação, dinâmica simbólica e teoria algébrica da lin-
guagem.
Endereço: Rua Dr. Efigênio Barbosa, 387
Bancários
João Pessoa – PB, Brasil
C.E.P.: 58.052 – 310
e-mail: ddselec@click21.com.br
Esta dissertação foi diagramada usando L
A
T
E
X2
ε
1
pelo autor.
1
L
A
T
E
X2
ε
é uma extensão do L
A
T
E
X. L
A
T
E
X é uma coleção de macros criadas por Leslie Lamport para o sistema T
E
X, que foi desen-
volvido por Donald E. Knuth. T
E
X é uma marca registrada da Sociedade Americana de Matemática (A
M
S). O estilo usado na formatação
desta dissertação foi escrito por Dinesh Das, Universidade do Texas. Modificado em 2001 por Renato José de Sobral Cintra, Universidade
Federal de Pernambuco, e em 2005 por André Leite Wanderley.
74
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
