A maior rede de estudos do Brasil

Grátis
271 pág.
Apostila LF

Pré-visualização | Página 10 de 49

um símbolo da palavra na entrada
e realizam uma transição com este símbolo. No caso de um AFND, ele também
tem a opção de realizar ε-transições entre os incrementos do relógio. Vamos então,
com esta ideia em mente, mostrar abaixo os possíveis estados em que cada um dos
autômatos pode estar durante uma computação com a palavra w = 0011 em cada
54 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
um dos instantes de tempo t = 0 até t = 4. Como um símbolo da palavra é consu-
mido em cada incremento de tempo, o processamento da palavra é concluído em
t = 4.
Vamos mostrar primeiro os possíveis estados em que o AFD descrito acima
pode estar em cada um dos instantes de tempo.
0
**
?�
�O
�O
�O
�O
�O
�O
�O
0
**
?�
�O
�O
�O
�O
�O
�O
�O
1
**
?�
�O
�O
�O
�O
�O
�O
�O
1
**
?�
�O
�O
�O
�O
�O
�O
�O
WVUTPQRSq1 // WVUTPQRSq2 // WVUTPQRSq1 // WVUTPQRSq1 // WVUTPQRSq1
Vemos que com uma transição determinística, existe sempre exatamente uma
única possibilidade de estado em que o autômato pode estar em cada instante de
tempo. Vamos agora mostrar os possíveis estados em que o AFND descrito acima
pode estar em cada instante de tempo.
0
**
?�
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
0
**
?�
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
1
**
?�
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
1
**
?�
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
�O
WVUTPQRSq1 //
��
✾✾
✾✾
✾✾
✾✾
✾✾
✾✾
✾✾
✾
WVUTPQRSq2 // WVUTPQRSONMLHIJKq4 //
ε
��
WVUTPQRSONMLHIJKq4 //
ε
��
WVUTPQRSONMLHIJKq4
ε
��WVUTPQRSq3
%%❑❑
❑❑❑
❑❑❑
❑❑
WVUTPQRSq3
WVUTPQRSq3 // WVUTPQRSq3 // WVUTPQRSq2 WVUTPQRSq2
Vemos que, no caso de uma transição não-determinística, em alguns instantes
de tempo, existem mais do que uma possibilidade de estado onde o autômato pode
estar, dependendo das escolhas aleatórias realizadas por eles. Entretanto, anali-
sando o diagrama acima, sabemos que, se o AFND está no estado q1, então, após
2. ALGORITMO DE CONSTRUÇÃO DE SUBCONJUNTOS 55
consumir um símbolo 0, ele estará em um dos estados do conjunto {q2, q3}. Analo-
gamente, se o AFND está em um dos estados do conjunto {q2, q3, q4}, então, após
consumir um símbolo 1, ele continuará em um dos estados do conjunto {q2, q3, q4}.
Desta forma, se passarmos a pensar em termos de conjuntos de estados do
AFND ao invés de em termos de estados individuais, nos tornamos capazes de
descrever as transições de forma completamente determinada, como representado
abaixo:
{q1}
0
→ {q2, q3}
0
→ {q3, q4}
1
→ {q2, q3, q4}
1
→ {q2, q3, q4}.
Esta é a ideia que utilizamos para construir um AFD Ad que aceita a mesma
linguagem que um dado AFND A. Os estados de Ad serão todos os possíveis
conjuntos de estados de A. Isto é, se o conjunto de estados de A é Q, então o
conjunto de estados de Ad será P(Q).
Para que uma palavra seja aceita pelo AFND, deve existir ao menos uma com-
putação finita no autômato que processe a palavra inteira e termine em um estado
final. Dito de outra forma, uma palavra será aceita se o conjunto de estados onde o
autômato pode estar no instante final de tempo (o instante após o processamento do
último símbolo) contiver ao menos um estado final do AFND. Desta forma, como
queremos que o AFND A e o AFD Ad aceitem as mesmas palavras, se F é o con-
junto de estados finais de A e S é um estado de Ad (S é um conjunto de estados de
A), S será estado final de Ad se S ∩ F 6= ∅.
Já descrevemos os conjuntos Qd e F d do AFD Ad. Para descrevermos qd0
e δ, precisamos de uma maneira de descrever as ε-transições que podem ocorrer
no AFND entre os incrementos do relógio. Seja S um conjunto de estados de
A. Definimos o conjunto E(S) como o conjunto de todos os estados alcançáveis
a partir de algum estado do conjunto S por uma sequência de zero ou mais ε-
transições, isto é, E(S) = {p ∈ Q : (q, ε) ⊢∗ (p, ε), onde q ∈ S}.
EXEMPLO 4.14. No AFND do exemplo anterior, temos E({q1}) = {q1},
uma vez que não há ε-transições saindo de q1. Analogamente, E({q2}) = {q2} e
E({q3}) = {q3}. Já no caso de q4, temos uma ε-transição saindo para q3. Então,
56 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
E({q4}) = {q3, q4}. Com estes conjuntos, podemos calcular E(S) para qual-
quer conjunto S de estados do AFND (S ⊆ Q). Por exemplo, E({q2, q4}) =
{q2, q3, q4}.
OBSERVAÇÃO. Repare que, para qualquer conjunto S, sempre temos S ⊆
E(S), uma vez que consideramos a possibilidade de zero ou mais ε-transições.
O estado inicial qd0 de Ad será o conjunto de todos os estados onde o AFND
A poderá estar no instante de tempo t = 0. Este conjunto é formado pelo estado
inicial q0 de A e por todos os estados que podem ser alcançados a partir de q0 por
ε-transições. Isto é, qd0 = E({q0}).
Finalmente, vamos descrever as transições de Ad, isto é, a função δ. Se S é um
estado de Ad (S é um conjunto de estados de A), e σ ∈ Σ, o estado T = δ(S, σ)
será justamente o conjunto de possíveis estados em que o AFND A poderá estar no
próximo instante de tempo, como ilustrado no diagrama acima. Para calcular T ,
procedemos em duas etapas. Primeiramente, para cada estado q ∈ S de A, calcu-
lamos o conjunto de estados ∆(q, σ) e tomamos a união de todos estes conjuntos.
Vamos denotar este novo conjunto por S′. S′ contém os possíveis estados em que
o AFND A poderá estar após o incremento no relógio. Entretanto, este não é ainda
o conjunto de todos os possíveis estados onde A pode estar neste novo instante de
tempo, pois nos resta ainda a possibilidade de A realizar ε-transições. Desta forma,
o conjunto T será T = E(S′).
Resumidamente, temos abaixo a lista dos componentes Qd, qd0 , F d e δ de Ad
dados em função dos componentes Q, q0, F e ∆ do AFND original A.
• Qd = P(Q);
• qd0 = E({q0});
• F d = {S ∈ Qd : S ∩ F 6= ∅} e
• δ(S, σ) = E(∪q∈S∆(q, σ)).
Vemos pela construção acima que, apesar de todo AFND possuir um AFD
equivalente, no sentido de que ambos aceitam a mesma linguagem, o AFD poderá
2. ALGORITMO DE CONSTRUÇÃO DE SUBCONJUNTOS 57
ter um tamanho exponencialmente maior do que o AFND original (já que se |Q| =
n, |Qd| = |P(Q)| = 2n).
Entretanto, nem sempre todos os estados no conjunto P(Q) são realmente ne-
cessários. Todos os estados de Qd que não podem ser alcançados a partir do estado
inicial qd0 podem ser removidos de Ad sem nenhum prejuízo. Isto nos sugere que
a melhor abordagem para a construção do AFD Ad é uma abordagem incremental.
Começamos com o estado inicial qd0 e calculamos as suas transições. Vemos quais
novos estados aparecem como resultado destas transições e repetimos este processo
com os novos estados. Continuamos assim até que não surjam mais novos estados
como resultado do cálculo das transições.
Vamos ilustrar esta abordagem incremental através de exemplos.
EXEMPLO 4.15. Vamos construir o AFD equivalente ao AFND descrito no
exemplo acima. Começamos calculando o estado inicial qd0 = E({q0}) = E({q1})
= {q1}, já que não existem ε-transições saindo de q1. Logo, vamos iniciar nossa
tabela de transições da função δ do nosso AFD com a linha
δ 0 1
{q1}
Vamos calcular δ({q1}, 0) e δ({q1}, 1).
δ({q1}, 0) = E(∪q∈{q1}∆(q, 0)) = E(∆(q1, 0)) = E({q2, q3}) = {q2, q3}.
δ({q1}, 1) = E(∪q∈{q1}∆(q, 1)) = E(∆(q1, 1)) = E({q3}) = {q3}.
Assim, surgiram dois novos estados após o cálculo destas transições: {q2, q3} e
{q3}. Adicionamos estes estados à tabela e continuamos os cálculos para estes
novos estados.
δ 0 1
{q1} {q2, q3} {q3}
{q2, q3}
{q3}
δ({q2, q3}, 0) = E(∪q∈{q2,q3}∆(q, 0)) = E(∆(q2, 0) ∪∆(q3, 0)) =
58 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
= E({q4}

Crie agora seu perfil grátis para visualizar sem restrições.