Apostila LF

cada par formado por um estado do conjunto Q e um sím-
bolo do alfabeto Σ ou o símbolo ε, a função de transição fornece como
resposta um conjunto de elementos de Q.
OBSERVAÇÃO. P(Q) denota o conjunto das partes de Q, ou seja, o conjunto
dos subconjuntos de Q. Como Q é um conjunto finito, se Q possui n elementos,
P(Q) possui 2n elementos.
EXEMPLO 4.2. Se S = {1, 2, 3}, então
P(S) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
OBSERVAÇÃO. Nestas notas, sempre iremos diferenciar funções de transição
determinísticas e não-determinísticas através da notação. Utilizamos uma letra
delta minúscula (δ) para transições determinísticas e uma letra delta maiúscula (∆)
para transições não-determinísticas.
45
46 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
Vamos analisar as diferenças entre a função de transição δ : Q × Σ → Q de
um AFD e a função de transição ∆ : Q× (Σ ∪ {ε})→ P(Q) de um AFND.
A resposta da função δ é um elemento do conjunto Q, ou seja, é um estado do
AFD para onde o autômato irá ao executar a transição. Já a resposta da função ∆ é
um elemento do conjunto P(Q), ou seja, é um conjunto de estados do AFND. Este
conjunto de estados representa as possibilidades de estados para onde o autômato
poderá ir ao executar a transição. Isto significa que, quando um AFND executa uma
transição, o estado para onde ele vai é escolhido aleatoriamente dentre o conjunto
de possibilidades oferecido pela resposta da função de transição. Esta é uma das
fontes de não-determinismo do autômato.
Outra diferença entre a função de transição determinística e a função de transi-
ção não-determinística está nas entradas destas funções. A entrada da função deter-
minística δ é sempre um par formado por um estado do autômato e um símbolo do
alfabeto. Já a entrada da função não-determinística ∆ admite duas possibilidades:
a primeira é um par no mesmo formato anterior e a segunda é um par formado por
um estado do autômato e o símbolo ε. As transições com entrada neste segundo
formato oferecem ao AFND a possibilidade de mudar de estado sem consumir ne-
nhum símbolo da palavra sendo processada pelo autômato, uma possibilidade que
não existia nos AFD’s. Esta é uma segunda fonte de não-determinismo do autô-
mato.
Vamos analisar um exemplo concreto de AFND.
EXEMPLO 4.3. Seja A o AFND A = (Σ, Q, q0, F,∆), onde:
• Σ = {0, 1};
• Q = {q1, q2, q3, q4};
• q0 = q1;
• F = {q4};
• A função ∆ é dada pela tabela abaixo.
1. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS (AFND’S) 47
∆ 0 1 ε
q1 {q2, q3} {q3} ∅
q2 {q4} ∅ ∅
q3 {q3} {q2} ∅
q4 {q1, q2} {q4} {q3}
A partir desta tabela, temos que ∆(q1, 0) = {q2, q3}, ∆(q1, 1) = {q3}, ∆(q1,
ε) = ∅ e assim por diante. Isto significa que, se o autômato está atualmente no
estado q1 e o próximo símbolo da palavra a ser processado é 0, a função de tran-
sição ∆ oferece duas possibilidades para o próximo estado do autômato: q2 ou q3.
O autômato irá então escolher aleatoriamente entre estas duas possibilidades. Já
se o autômato está atualmente no estado q1 e o próximo símbolo da palavra a ser
processado é 1, a função de transição ∆ oferece apenas uma possibilidade para o
próximo estado do autômato: q3. Desta forma, este será certamente o estado do
autômato após executar a transição. Finalmente, como ∆(q1, ε) = ∅, isto significa
que a função de transição ∆ não oferece nenhuma possibilidade para que o autô-
mato, estando em q1, faça uma mudança de estado sem consumir nenhum símbolo
da palavra sendo processada.
Analisando um pouco mais a tabela, temos que ∆(q2, 1) = ∆(q2, ε) = ∅.
Desta forma, se o autômato está atualmente no estado q2 e o próximo símbolo da
palavra a ser processado é 1, então a função ∆ não oferece nenhuma possibilidade
de transição para o autômato. O autômato não pode consumir o símbolo 1 e mudar
de estado porque ∆(q2, 1) = ∅ e também não pode mudar de estado sem consumir
nenhum símbolo da palavra porque ∆(q2, ε) = ∅. Assim, caso o autômato esteja
no estado q2 e o próximo símbolo da palavra seja 1, ele irá travar sem completar o
processamento da palavra. Um AFD sempre processa a palavra que recebe como
entrada completamente. Vemos que isto pode não acontecer em todos os casos com
um AFND.
Para finalizar a análise da tabela, temos que ∆(q4, 0) = {q1, q2} e ∆(q4, ε) =
{q3}. Desta forma, se o autômato está atualmente no estado q4 e o próximo sím-
bolo da palavra a ser processado é o 0, ele tem a possibilidade de duas escolhas
48 4. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS
aleatórias para realizar com relação ao seu próximo estado. A primeira escolha é
se ele irá realizar a transição consumindo o símbolo 0 ou se irá realizar a transição
sem consumir nenhum símbolo da palavra que está processando. Caso ele opte
pela segunda alternativa, como apenas q3 está no conjunto ∆(q4, ε), o autômato
irá para o estado q3. Caso ele opte pela primeira alternativa, ele irá então realizar
uma escolha aleatória entre os dois estados que a transição ∆(q4, 0) oferece como
possibilidades: q1 e q2.
DEFINIÇÃO 4.4. As transições da forma ∆(q, ε), para algum q ∈ Q, são
chamadas de ε-transições.
OBSERVAÇÃO. Um AFND também admite uma representação através de um
grafo direcionado com arestas rotuladas, de maneira análoga à representação dos
AFD’s. Os símbolos do conjunto Σ ∪ {ε} aparecem como rótulos das arestas do
grafo, que são rotuladas de acordo com a função de transição ∆. Se, para um
determinado q ∈ Q e para um determinado γ ∈ Σ ∪ {ε}, temos q′ ∈ ∆(q, γ)
(lembrando que ∆(q, γ) é um conjunto), então colocamos no grafo uma aresta
direcionada do vértice de q para o vértice de q′ e rotulamos esta aresta com o
símbolo γ.
EXEMPLO 4.5. O grafo que representa o AFND do exemplo anterior é mos-
trado abaixo.
I // WVUTPQRSq1
0
,,
1
��
0
��
WVUTPQRSq2
0
��WVUTPQRSq3
0
\\
0
CC
WVUTPQRSONMLHIJKq4
ε
oo
1
\\
0
RR
1
[[
OBSERVAÇÃO. Ao representarmos a função de transição ∆ na forma de ta-
bela, o não-determinismo da transição se traduz no fato de que a tabela é agora pre-
enchida por subconjuntos de Q e não mais por elementos de Q como nos AFD’s.
Um caso particular importante de se salientar é que alguns campos da tabela podem
ser preenchidos com o conjunto vazio (∅) que denota a ausência de possibilidades
1. AUTÔMATOS FINITOS NÃO-DETERMINÍSTICOS (AFND’S) 49
de transição. Já ao representarmos o AFND como um grafo, o não-determinismo
da transição se traduz na liberdade para que um vértice tenha várias arestas rotu-
ladas por um mesmo símbolo saindo dele ou mesmo para que não tenha nenhuma
aresta rotulada por um dado símbolo saindo dele.
Um AFND também processa uma palavra que recebe como entrada e fornece
como saída uma resposta do tipo Sim/Não. O AFND A = (Σ, Q, q0, F,∆) inicia
seu processamento no estado q0 e recebe como entrada uma palavra w ∈ Σ∗. Ele
lê um símbolo de w de cada vez, começando pelo seu primeiro símbolo mais à
esquerda. Se o autômato se encontra em um estado q, ele pode ir para algum
estado q′ ∈ ∆(q, ε) sem ler nenhum símbolo da entrada (desde que ∆(q, ε) 6= ∅)
ou ele pode ler o próximo símbolo da entrada (denotado por σ) e, após a leitura,
ele irá para algum estado q′′ ∈ ∆(q, σ).
A partir destas transições de estado, podemos definir a noção de uma compu-
tação do autômato com uma palavra w.
DEFINIÇÃO 4.6. Uma configuração do AFND A é um par formado por um
estado deA e uma palavra deΣ∗ (um elemento deQ×Σ∗). O primeiro componente
de uma configuração representa o estado atual do autômato, enquanto o segundo
componente representa o trecho da palavra de entrada que ainda não foi lida pelo
autômato.
DEFINIÇÃO 4.7. A relação de configuração seguinte (notação ⊢) é definida
como (q, w) ⊢ (q′, w′) se
(1) w = σw′ e q′ ∈ ∆(q, σ) OU
(2) w = w′ e q′ ∈ ∆(q, ε).
OBSERVAÇÃO.