Apostila LF

Em um AFD, cada configuração (q, w) possui exatamente
uma configuração seguinte, se w 6= ε, ou nenhuma configuração seguinte no caso
em que w = ε. Já em um AFND, uma configuração (q, w) pode possuir uma,
várias ou mesmo nenhuma configuração seguinte.
50 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
DEFINIÇÃO 4.8. Se C0, . . . , Cn são configurações de A e se C0 ⊢ . . . ⊢ Cn,
então temos uma computação em A, notação C0 ⊢∗ Cn (em particular, assumimos
que C0 ⊢∗ C0).
OBSERVAÇÃO. Como uma configuração pode possuir várias configurações
seguintes, o autômato pode ter a possibilidade de realizar diversas computações
distintas com uma mesma palavra w. Devido às ε-transições, é possível também
a existência de computações infinitas em um AFND, o que nunca pode acontecer
em um AFD. Finalmente, devido à possibilidade de que a resposta para algumas
transições seja o conjunto vazio, é possível a existência de computações em um
AFND que travam sem conseguir ler a palavra da entrada completamente, algo que
nunca acontece em um AFD.
Como uma mesma palavra w pode produzir diversas computações distintas em
um AFND, a questão de quando uma palavra é ou não aceita pelo autômato se torna
mais sutil. Algumas computações com w podem ser infinitas, outras podem travar
sem ler w completamente, outras ainda podem ler w completamente e terminarem
em um estado que não é final e, finalmente, outras podem ler w completamente
e terminarem em um estado que é final. Como classificamos w neste caso? Esta
palavra é aceita ou rejeitada?
A definição abaixo estabelece os critérios que utilizaremos para determinar se
uma palavra é ou não aceita por um AFND.
DEFINIÇÃO 4.9. Dizemos que uma palavra w ∈ Σ∗ é aceita ou reconhecida
pelo AFND A se existe pelo menos uma computação finita (q0, w) ⊢∗ (f, ε) onde
f ∈ F . Isto é, uma palavra w é aceita se existe pelo menos uma computação finita
tal que
(1) w é completamente lida E
(2) O AFND termina a computação em algum de seus estados finais.
Caso contrário, dizemos que a palavra é rejeitada ou não aceita ou não reconhecida
pelo AFND A.
1. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS (AFND’S) 51
OBSERVAÇÃO. É importante ressaltar que uma computação em que o autô-
mato trava sem conseguir ler a palavra w completamente nunca é uma computação
que satisfaz os critérios acima, mesmo que o travamento ocorra em um dos estados
finais do autômato.
OBSERVAÇÃO. Vemos que as definições de aceitação e rejeição são de certa
forma assimétricas em um AFND. Para uma palavra w ser aceita, basta que uma
computação satisfaça os critérios acima. Já para uma palavra w ser rejeitada, é
necessário que todas as possíveis computações com w não satisfaçam os critérios
acima.
DEFINIÇÃO 4.10. Definimos a linguagem aceita por um AFND A com alfa-
beto Σ, denotada por L(A), como sendo o conjunto de todas as palavras w ∈ Σ∗
que são aceitas por A. Observe que temos L(A) ⊆ Σ∗.
EXEMPLO 4.11. Consideramos o autômato descrito no exemplo anterior. Va-
mos descrever o comportamento do autômato ao receber como entrada a palavra
w1 = 11101.
(q1, 11101) ⊢ (q3, 1101) ⊢ (q2, 101) ⊢ X
Graficamente:
WVUTPQRSq1 1 // WVUTPQRSq3 1 // WVUTPQRSq2 1 // WVUTPQRSX
Não existe nenhuma outra computação possível neste autômato para a palavra w1
e esta computação trava sem processar a parte 101 da palavra. Logo, esta palavra
não é aceita pelo autômato.
EXEMPLO 4.12. Consideramos o autômato descrito no exemplo anterior. Va-
mos descrever o comportamento do autômato ao receber como entrada a palavra
w2 = 0011. Neste caso, temos diversas possibilidades de computações neste autô-
mato para a palavra w2. Vamos descrevê-las.
(1) (q1, 0011) ⊢ (q2, 011) ⊢ (q4, 11) ⊢ (q4, 1) ⊢ (q4, ε)
(2) (q1, 0011) ⊢ (q2, 011) ⊢ (q4, 11) ⊢ (q4, 1) ⊢ (q4, ε) ⊢ (q3, ε)
(3) (q1, 0011) ⊢ (q2, 011) ⊢ (q4, 11) ⊢ (q4, 1) ⊢ (q3, 1) ⊢ (q2, ε)
52 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
(4) (q1, 0011) ⊢ (q2, 011) ⊢ (q4, 11) ⊢ (q3, 11) ⊢ (q2, 1) ⊢ X
(5) (q1, 0011) ⊢ (q3, 011) ⊢ (q3, 11) ⊢ (q2, 1) ⊢ X
Vemos que destas cinco computações possíveis, duas travam sem ler a palavra w2
completamente, duas leem toda a palavra e terminam em estados que não são finais
(q3 e q2) e uma lê toda a palavra e termina em um estado final (q4). Desta forma,
como existe pelo menos uma computação finita que lê toda a palavra e termina
em um estado final, a palavra w2 é aceita pelo autômato. De fato, uma vez que a
computação que aceita w2 foi logo a primeira descrita e precisamos de apenas uma
computação desta forma para determinar que a palavra é aceita, temos que para
efeitos práticos era desnecessário ter calculado as demais computações possíveis.
OBSERVAÇÃO. Um AFD é um caso particular de um AFND. Considere um
AFND em que a função de transição ∆ satisfaz as seguintes propriedades:
(1) ∆(q, ε) = ∅, para todo q ∈ Q E
(2) ∆(q, σ) é um conjunto unitário para todo par (q, σ), onde q ∈ Q e σ ∈ Σ.
Neste caso, o que temos na prática é um AFD escrito no “formato” de um AFND,
uma vez que retiramos todas as possibilidades de não-determinismo. Logo, um
AFD é um caso particular de um AFND.
2. Algoritmo de Construção de Subconjuntos
Vimos, na seção anterior, que um AFD é um caso particular de um AFND.
Desta forma, as linguagens que são aceitas por algum AFD (as linguagens re-
gulares) são aceitas também por algum AFND. Entretanto, será que a recíproca
também é verdadeira? Isto é, será que qualquer linguagem L que seja aceita por
algum AFND também será aceita por algum AFD ou os AFND’s são capazes de
aceitar algumas linguagens que estão fora da classe das linguagens regulares?
É indiscutível que a transição não-determinística possui muito menos amarras
do que a transição determinística. Isto parece indicar que AFND’s podem ser capa-
zes de aceitar algumas linguagens que não sejam aceitas por AFD’s ao se utilizarem
dessa flexibilidade maior de suas funções de transição. Entretanto, provavelmente
no sentido inverso da intuição inicial da maioria das pessoas, isto não é verdade.
2. ALGORITMO DE CONSTRUÇÃO DE SUBCONJUNTOS 53
Mesmo com esta flexibilização nas funções de transição, os AFND’s não possuem
maior poder computacional do que os AFD’s, isto é, se existir um AFND que aceite
uma dada linguagem L, também existe um AFD que aceita L.
Vamos mostrar este resultado de forma algorítmica, isto é, dado um AFND
A = (Σ, Q, q0, F,∆), vamos descrever um algoritmo que permite construir, a par-
tir dos componentes de A, um AFD Ad = (Σ, Qd, qd0 , F d, δ) tal que L(Ad) =
L(A). Isto significa que o AFD Ad construído pelo algoritmo aceita exatamente a
mesma linguagem que o AFND A original, porém sem fazer uso de qualquer tipo
de não-determinismo. Este algoritmo que permite calcular o AFD Ad a partir do
AFND A é conhecido como Algoritmo de Construção de Subconjuntos.
Para compreendermos como podemos representar o comportamento de um
AFND utilizando apenas transições determinísticas, vamos analisar em paralelo a
computação de dois autômatos: um determinístico, que foi descrito em um exem-
plo no capítulo 2, e um não-determinístico, descrito no exemplo acima.
EXEMPLO 4.13. Colocamos abaixo os grafos destes dois autômatos.
I // WVUTPQRSq1
0
,,
1
BB
WVUTPQRSq2
0
ll
1~~⑥⑥
⑥⑥
⑥⑥
WVUTPQRSONMLHIJKq31
``❆❆❆❆❆❆
0
\\
I // WVUTPQRSq1
0
,,
1
��
0
��
WVUTPQRSq2
0
��WVUTPQRSq3
0
\\
0
CC
WVUTPQRSONMLHIJKq4
ε
oo
1
\\
0
RR
1
[[
Vamos imaginar agora, apenas para efeito de melhor compreensão, que as com-
putações nestes autômatos são controladas por um relógio que começa a contagem
de tempo no instante t = 0 e a cada novo “instante” de tempo, aumenta sua conta-
gem em uma unidade, isto é, t = 1, t = 2 e assim por diante. A cada incremento na
contagem do relógio, os autômatos consomem