Conversão AFN para AFD
Expressões Regulares
Algoritmos OR em ER
Conversão de ER para AFN
Conversão de AFD para ER
Conversão AFN → AFD
 Já sabemos que todo AFN tem um AFD equivalente
mas como encontrá-lo?
 Para esse problema temos um algoritmo.
Conversão AFN → AFD
 Algoritmo
 Cria-se o estado inicial do AFD com o estado inicial do
AFN e os estados atingidos por transições ε.
 Compute para os estados criados as saídas para cada
estado que faz parte dele para todas as entradas do
alfabeto através da função de transição e das transições ε,
una os estados resultantes e crie um novo estado. Faça
isso até que não se crie mais estados novos, ou seja, o
AFD está completo.
 Os estados finais do AFD é todo estado que possui pelo
menos um estado de aceitação do AFN.
Conversão AFN → AFD
 Exemplo
AFN
AFD
ε
1
2
0
1,2
0
Computando δ({1,2},0)
0,1
0
3
1
0
Estado inicial que
é 1 e tem
transição ε para 2
1
3
2
1,2
1,2,3
Computando δ({1,2},1)
1
Conversão AFN → AFD
1
Ø
2
Ø
 Exemplo
AFN
AFD
ε
1
2
0
1,2
0,1
0
3
Ø
1
1
0
1,2,3
0,1
Computando δ({1,2,3},0)
0
Conversão AFN -> AFD
 Exemplo
AFN
AFD
ε
1
2
0
1,2
0
0,1
0
3
1
1
Ø
0,1
1
3
2
1,2
3
Ø
1,2,3
1,2,3
0
Computando δ({1,2,3},1)
1
Conversão AFN → AFD
 Exemplo
AFN
AFD
ε
1
2
0
1,2
0
1,2,3
3
1
1
1
Ø
0,1
Ø
2
Ø
3
2,3
2,3
0,1
0
1
0
Computando δ({2,3},0)
0
Conversão AFN → AFD
2
1,2
3
Ø
 Exemplo
AFN
AFD
ε
1
2
0
0
1,2
1,2
1,2,3
0,1
0
3
1
1
0
Ø
0,1
1
2,3
0
Computando δ({2,3},1)
1
Conversão AFN → AFD
2
Ø
3
2,3
 Exemplo
AFN
AFD
ε
1
2,3
2
0
0
1,2
0
1,2,3
0,1
0
3
1
1
0
Ø
0,1
Não há mais estado sem transição definida
1
2,3
1
Conversão AFN → AFD
 Exemplo
AFN
AFD
ε
1
2
0
0
1,2
0
1,2,3
0,1
0
3
1
1
0
Ø
0,1
Onde houver estado de aceitação, no caso 2,
também será estado de aceitação
1
2,3
1
Exercícios AFN → AFD
1.
2.
Expressão Regular
 Definição
 É uma forma de definir uma Linguagem Regular como
uma expressão.
 Definição Indutiva
 Base

ε, Ø e os elementos do alfabeto
 Indução: Sejam A e B ERs



A∪B também é ER.
A∘B ou AB, também é.
A* também é ER
Expressão Regular
 Teoremas
 Toda ER gera uma LR.
 Toda LR tem uma ER que a reconhece univocamente.
 Toda ER tem um AFN equivalente
Operações Regulares
 União
 A união de duas ERs, representada por A∪B
 Concatenação
 A concatenação de duas ERs, representada por A∘B ou AB
 Estrela
 A estrela de uma ER, representada por A*
Conversão LR → ER
 Semelhante a conversão LR -> AFD só que tem que
pensar na ER não mais no AFD, não há algoritmo.
 Exemplos
 L = {w| w tem tamanho par}

ER= (∑ ∑)*
 L = {w| w só tem 0 antes de 1}

ER = 0+1*, o + significa um ou mais 0+ = 00*.
 L = {0, 11, 0000}

ER = 0 ∪11 ∪0000
 L={w| w tem um único 0}

ER = 1*01*
Exercícios LR → ER
L = {0, 11, 000}
2. L = {w| começa e termina com a letras diferentes}
3. L = {w| termina com 101 e tem 010 como subcadeia}
4. L = {w| w não tem a subcadeia 01}
1.
Conversão ER → AFN
 Caso ER = Ø
 Caso ER = ε
 Seja ER = a, onde a é um elemento de ∑
 União, Concatenação e Estrela
 Iguais aos algoritmos de AFN
Conversão ER → AFN
 Exemplos
 Ø∪ε
 1+0*
Exemplos ER → AFN
1.
0(011)*∪1
2. 0+∪(01)+
3.
∑*000∑*
4. (((00)*11)∪01)*
Conversão AFD → ER


Sabemos que uma LR pode ser representada por
AFD, AFN e ER que são equivalentes entre si.
Já podemos converter ER → AFN → AFD, só falta
converter AFD → ER, para esse processo temos
algoritmo.
Conversão AFD → ER
 Algoritmo
 Crie um novo estado inicial e uma transição ε para o
estado inicial do AFD
 Crie um novo estado de aceitação e crie transições ε dos
estados de aceitação do AFD para este novo estado e tire
as antigas aceitações, agora temos um Autômato Finito
Não-Determinístico Generalizado (AFNG).

Um AFNG possui ER nas transições não só uma letra.
 Elimine os estados do AFD um por vez até que só fique a
ER do novo estado inicial até o novo estado de aceitação.
Conversão AFD → ER
 Algoritmo
 Elimine os estados do AFD um por vez segundo a regra
 Faça isso até eliminar todos os estados do AFD
 Ao fim disso tudo, só temos uma transição com a ER do
AFD inicial.
Conversão AFD → ER
 Exemplo
ε
0
1
0
2
ε
S
ε
1
0
3
0,1
1
ε
4
1
a
Conversão AFD → ER
 Exemplo
ε
0
1
0
2
ε
S
ε
1
0
3
0,1
1
ε
4
a
1
Cortar um estado vazio não causa
alterações no autômato
Conversão AFD → ER
 Exemplo
ε
0
1
0
2
ε
S
ε
0
11*
ε
1
11*0
4
a
1
Neste estado passa informação de 2 → 1 e de 2 → a
Conversão AFD → ER
 Exemplo
ε
1
0
ε
2
0
ε
11*∪ ε
11*
S
11*0
União
a
Conversão AFD → ER
 Exemplo
00*11*0
ε
1
0
2
0
ε
00*(11*∪ ε) 11*∪ ε
S
a
11*0
Neste estado passa informação de 1 → 1 e de 1 → a
Conversão AFD → ER
 Exemplo
00*11*0
ε
1
ε
S
(00*(11*∪ ε)) ∪ ε
00*(11*∪ ε)
União
a
Conversão AFD → ER
 Exemplo
00*11*0
1
ε
S
(00*(11*∪ ε)) ∪ ε
(00*11*0)*((00*(11*∪ ε)) ∪ ε)
Neste estado passa informação de S → a
a
Conversão AFD → ER
 Exemplo
S
(00*11*0)*((00*(11*∪ ε)) ∪ ε)
Está pronta a Expressão Regular
a
Exemplos AFD → ER
1.
2.
Exemplo
LR → AFD → ER → AFN → AFD
1.
L = {w ∈ ∑ | w tem um número ímpar de 1’s}
Obrigado!