Aulas5-8Automatos

Prévia do material em texto

Teoria da Computação 
Autômatos Finitos 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão 
 Um alfabeto é um conjunto finito de símbolos 
indivisíveis (ex.: caracteres) denotado por ∑ 
• ∑1 = {a, b, d, e, f, g, h, i, j, k, l, …, z} 
• ∑2 = {0, 1} 
 Uma palavra definida sobre um alfabeto ∑ é uma 
sequência finita de elementos em ∑ 
• p1 = ufla é uma palavra definida sobre ∑1 
• p2 = 00010100 é uma palavra definida sobre ∑2 
• P3 = 0311 não é uma palavra definida sobre ∑2 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (2) 
 Seja p é uma palavra definida sobre ∑, o 
comprimento de p, denotado por|p|, é o 
número de símbolos em ∑ contidos em p 
• p1 = ufla, |p1| = 4 
 Uma palavra de comprimento zero é chamada 
palavra vazia e denotada por 
• | | = 0 
 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (3) 
 Se p possui tamanho n, podemos escrever p 
como 𝑝1𝑝2…𝑝𝑛, onde cada 𝑝𝑖 ∈ ∑ 
 O reverso de 𝑝,denotado por 𝑝𝑅, é a palavra 
obtida através da escrita de p em ordem reversa 
• 𝑝1 = ufla, 𝑝1
𝑅= alfu 
 Uma palavra z é uma subpalavra de p se z 
aparece consecutivamente em p 
• fl é uma subpalabra de ufla 
• Se o primeiro símbolo de z coincide com o primeiro 
símbolo de p, dizemos que z é um prefixo de p 
• Se o último símbolo de z coincide com o último 
símbolo de p, dizemos que z é um sufixo de p 
 4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (4) 
 Se temos uma palavra x de comprimento m e 
uma palavra y de comprimento n, a concatenação 
de x com y, denotado como xy, é a palavra 
formada através da anexação de y ao final de x 
• 𝑝1 = ufla, 𝑝2 = lavras, 𝑝1𝑝2 = uflalavras 
• A concatenação de uma string múltiplas vezes consigo 
mesma é representada através de sobescrito, onde o 
valor no sobescrito corresponde ao número de 
concatenações 
• a5 = aaaaa 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (5) 
 A ordem lexicográfica de palavras é similar à 
ordem alfabética; a única diferença é que 
palavras mais curtas possuem precedência 
sobre palavras mais longas 
• A ordenação das palavras definidas sobre o 
alfabeto {0,1} é { , 0, 1, 00, 01, 10, 11, 000, …} 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (6) 
 Uma linguagem é um conjunto de palavras 
 As palavras que compõem uma linguagem 
devem satisfazer certas propriedades (para 
que a linguagem tenha alguma utilidade) 
 Estas propriedades definem a sintaxe da 
linguagem 
 Linguagens podem ser usadas para expressar 
algoritmos e instâncias de problemas a serem 
computados 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Breve Revisão (7) 
 Um modelo computacional é uma abstração de 
um computador, em outras palavras, um 
computador idealizado 
• Conjuntos básicos de operações, operandos, e 
recursos bem definidos 
• Evita ater-se a aspectos de um hardware específico 
• Possibilita o desenvolvimento de uma teoria 
matemática 
• O modelo computacional mais simples que iremos 
estudar é chamado máquina de estados finitos ou 
autômato finito 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Autômatos Finitos 
 Características (informais): 
• Conjunto finito de estados 
• Toda computação tem um estado salvo 
• Memória finita 
• Alguns eventos causam a alteração do estado 
 Modelo computacional adequado para 
representar computadores com memória 
extremamente limitada como muitos 
dispostivos eletromecânicos 
 
 9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo: Porta Automática 
10 
Sensor dianteiro Sensor traseiro 
Porta 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Porta Automática: Descrição 
 O controlador possui dois estados: ABERTO e 
FECHADO 
 Quatro sinais causam transições de estados: 
• Frente – uma pessoa encontra-se na área de 
cobertura do sensor dianteiro 
• Verso – uma pessoa encontra-se na área de cobertura 
do sensor traseiro 
• Nenhum – ninguém encontra-se na área de cobertura 
de qualquer sensor 
• Ambos – pessoas encontram-se na área de cobertura 
de ambos os sensores 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Porta Automâtica: 
Tabela de Transição de Estados 
12 
Aberto 
Fechado 
Nenhum Frente Verso Ambos 
Fechado 
Fechado 
Aberto 
Aberto 
Aberto 
Fechado 
Aberto 
Fechado 
Estados Sinais de entrada 
Qual a sequência de transições de estados gerada pela seguinte sequência de 
sinais recebidos a partir do estado FECHADO: 
{FRENTE, VERSO, NENHUM, FRENTE, FRENTE, AMBOS, VERSO, NENHUM} 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 13 
Aberto 
Porta Automâtica: 
Diagrama de Estados 
Nenhum 
Ambos 
Fechado 
Verso 
Frente 
Ambos 
Verso Frente 
Nenhum 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Controlador da Porta Automática = 
Automâto Finito 
 Recebe sequências de sinais de entrada; cada 
sinal conduz a uma transição de estados 
(transições podem ser entre um mesmo 
estado) 
 De maneira similar podemos representar 
outros dispositivos: elevadores, máquinas de 
lavar, cancelas automáticas, etc. 
 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Representação Gráfica 
15 
q1 q2 q3 
0 
1 
1 
0 
0,1 
Estado Final Estado Inicial 
Diagrama de Estados M1 
 Estados = {q1, q2, q3} 
 Estado inicial: q1 
• Seta vindo de nenhum estado e apontando para q1 
 Estado final: q2 
• Círculos duplos concêntricos 
 Transições: Setas indo de um estado para outro 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento de Palavras 
 Um autômato processa um palavra recebida 
como entrada e gera uma saída 
 Vamos considerar apenas duas saídas: Aceita ou 
Rejeita 
 Símbolos processados da esquerda para a direita 
 Cada símbolo lido produz uma transição de 
estados 
 Quando o último símbolo é lido, o autômato 
produz a saída Aceita se o estado atual é o estado 
final; caso contrário, Rejeita 
• Resultado Aceita: o autômato aceita a palavra de 
entrada 
• Resultado Rejeita: o autômato rejeita a palavra de 
entrada 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Processamento de Palavras 
17 
q1 q2 q3 
0 
1 
1 
0 
1 
 Autômato recebe a palavra 1101 
• Resultado: Aceita 
 Verifique o resultado para estas palavras: 
• 00100, 11110000, 0101010 
0, 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal 
 Um autômato finito é representado pela 
quintupla Q, ∑, , q0, F , onde 
1. Q é um conjunto finito de estados 
2. ∑ é o alfabeto 
3. : Q ∑ Q, é uma função de transição 
4. 𝑞0 ∈ 𝑄 é o estado inicial 
5. 𝐹 Q é o conjunto de estados finais 
 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Descrevendo M1 
 Q = {q1, q2, q3} 
 ∑ = {0, 1} 
 = { (q1,0) = q1, (q1,1) = q2, (q2,0) = q3, 
(q2,1) = q2, (q3,0) = q2, (q3,1) = q2} 
 q1 é o estado inicial 
 F = {q2} 
19 
q1 q2 q3 
0 
1 
1 
0 
0,1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas e Linguagens 
 Se A é o conjunto de todas palavras que uma 
máquina (no caso atual, autômatos) aceita, então 
dizemos que A é a linguagem da máquina M, 
denotado por 𝐿 𝑀 = 𝐴. Também dizemos que 
M reconhece A 
• Usaremos o termo aceita para palavras e reconhece 
para linguagens 
 Uma máquina aceita várias palavras, mas 
reconhece apenas uma linguagem. Se uma 
máquina não aceita qualquer palavra, então ela 
reconhece a linguagem formada pelo conjunto 
vazio, isto é, 𝐿 𝑀 = 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas e Linguagens 
 Qual é a linguagem de M1, isto é, L(M1)? 
21 
q1 q2 q3 
0 
1 
1 
0 
0,1 
M1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Máquinas e Linguagens 
 Qual é a linguagem de M1, isto é, L(M1)? 
 Resposta: A = {p| p contém pelo menos um 
símbolo 1 e uma quantidade par de 0s após o 
último 1} 
• p.s. Considerando-se 0 como um número par 
 22 
q1 q2 q3 
0 
1 
1 
0 
0,1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (1) 
1. Qual é a descrição formal de M2? 
2. Qualé a linguagem de M2? 
 
23 
q1 q2 
0 
1 
1 
0 
M2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (1) 
1. Qual é a descrição formal de M2? 
• 𝑀2 = 𝑞1, 𝑞2 , 0,1 , , 𝑞1, 𝑞2 , é dada por 
 
 
 
 
 Qual é a linguagem de M2? 
• L(M2) = {p| p termina com 1} 
 
24 
0 1 
q1 q1 q2 
q2 q1 q2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (2) 
1. Qual é a “peculiaridade” de M3? 
2. Qual é a consequência desta peculiaridade? 
3. Qual é a linguagem de M3? 
25 
q1 
0 
q2 
1 
1 
0 
M3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (2) 
1. Qual é a “peculiaridade” de M3? 
• Estado inicial e final são o mesmo 
2. Qual é a consequência desta peculiaridade? 
• M3 aceita 
3. Qual é a linguagem de M3? 
• L(M2) = {p| p é ou termina em 0} 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
 Dado o alfabeto ∑2 = {0, 1}, projete um 
autômato finito que reconheça a seguinte 
linguagem: 
 A = {p| p inicia e termina com o mesmo símbolo} 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
28 
q0 
q1 
0 
0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
29 
q0 
q1 
0 
0 
q2 
1 
1 
0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
30 
q0 
q1 
0 
0 
q2 
1 
1 
0 
q2 1 
q3 
0 
0 
1 
1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (4) 
 O conjunto F pode ser vazio 
• Qual é a consequência? 
 A função de transição especifica exatamente 
um próximo estado para cada combinação 
entre estado e símbolo de entrada 
• Qual é a consequência? 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (4) 
 O conjunto F pode ser vazio 
• Qual é a consequência? 𝐿 𝑀 = 
 A função de transição especifica exatamente 
um próximo estado para cada combinação 
entre estado e símbolo de entrada 
• Qual é a consequência? Determinismo 
 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Dica Para o Projeto de 
Autômatos Finitos 
 Lembrem-se que a memória é finita! 
• Não é necessário (possível) “lembrar” toda a entrada 
(pode ser palavras de tamanho arbitrário) 
• Concentrem-se na informação que é crucial 
 Exemplo: Projete um automato finito que aceite todas 
palavras sobre o alfabeto ∑ = {0, 1} que contenham 
um número ímpar de 1s 
 Qual é a informação que precisa ser lembrada? 
 Apenas precisamos saber se a posição na sequência do último 
símbolo 1 lido até o momento é ímpar ou par 
 33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de Computação 
de Autômatos Finitos 
 Seja M = (Q, ∑, , q0, F) um autômato finito e p 
= 𝑝1𝑝2…𝑝𝑛 uma palavra sobre o alfabeto ∑. 
Então M aceita p se existe uma sequência de 
estados r0, r1, ..., rn em Q satisfazendo as três 
condições seguintes: 
1. r0 = q0, 
2. (ri, pi+1) = ri+1 para i=0,...,n, e 
3. 𝑟𝑛 ∈ 𝐹 
 M reconhece uma linguagem A se A = {p | M 
aceita p} 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (5) 
 Apresente o diagrama de estados de um AFD 
que reconheça a seguinte linguagem: L = {p | 
p contenha pelo menos dois as e no máximo 
um b. O alfabeto de entrada do AFD é ∑ = {a,b} 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (5) 
36 
q0 q1 q2 
b 
a 
a 
b 
b 
a 
q3 q4 q5 
a 
a 
a 
q6 
b 
b b 
a,b 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (6) 
 Apresente o diagrama de estados de um AFD 
que reconheça a seguinte linguagem: L = {p | 
p contenha exatamente dois as e um número 
impar de bs. O alfabeto de entrada do AFD é ∑ 
= {a,b} 
 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (6) 
38 
q0 q1 q2 
b 
a a 
q3 q4 q5 
a a 
b b b b b q6 
a 
a 
a,b 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Não-determinismo 
 Em máquinas não-determinísticas podem 
existir múltiplas escolhas para o próximo 
estado em qualquer ponto do processamento 
 Não-determinismo é uma generalização de 
determinismo: todo autômato finito 
determinístico (AFD) é automaticamente uma 
autômato finito não-determinístico (AFND) 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Características de AFNDs 
 Em um AFND, um estado pode ter 0, 1, ou 
muitas transições para cada símbolo 
 Em um AFND, transições podem ser 
disparadas por símbolos do alfabeto ou por 
• 0, 1, ou muitas setas podem deixar cada estado 
através de 
40 
q1 q2 q3 
0,1 
1 0, 
q4 
1 
0,1 N1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Como um AFND Computa? 
 Quando existe mais de uma transição de estado 
associada com o mesmo símbolo, o AFND se 
replica em múltiplas cópias e segue todas 
possibilidades em paralelo, uma transição 
diferente para cada cópia 
41 
q1 q2 
0,1 
1 
0001110 
q1 q2 
0,1 
1 
q1 q2 
0,1 
1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Como um AFND Computa? (2) 
 Quando não existe uma transição associada 
ao símbolo atual, a cópia do AFND 
simplesmente “morre” e sua ramificação de 
computação termina 
42 
q2 q3 
0, 
0001110 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Como um AFND Computa? (3) 
 Quando uma ou mais transições a partir do 
estado atual estão associadas com , o AFND se 
replica em múltiplas cópias, uma cópia para cada 
transição associada com e mais uma cópia que 
permanece na transição atual 
43 
q2 
0001110 
q3 
0, 
q2 
q3 
0, 
1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
AFND-𝜀 
 Alguns autores (e.g., Sudkamp) diferenciam 
entre AFNDs que não possuem uma transição 
de estados para símbolo e AFNDs que, além 
desta característica, também possuem 
transições envolvendo a palavra vazia 𝜀 
 Estes automâtos são chamados autômatos 
finitos com movimentos vazios e 
referenciados por AFND-𝜀 (ou NFA-𝜀, da sigla 
em inglês) 
 Neste curso não será feita esta distinção 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Como um AFND Computa (4) 
 Finalmente, o AFND aceita a entrada quando 
qualquer uma das cópias do AFND encontra-
se em um estado final após símbolo da 
entrada ter sido processado 
45 
q4 
0,1 0001110 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 Não-determinismo pode ser visto como uma 
forma de paralelismo, onde vários processos 
executam em paralelo; se pelo menos um 
destes processos aceita a entrada, então o 
resultado da completa computação é Aceita 
 Alternativamente, não-determinismo pode ser 
visto como uma árvore de possiblidades 
46 
Como um AFND Computa (5) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Computação Determinística vs. 
Não-Determinística 
47 
Determinístico 
aceita ou rejeita 
Não-Determinístico 
X 
... 
rejeita 
rejeita 
... 
... 
X 
aceita 
rejeita 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo de Computação 
48 
q1 q2 q3 
0,1 
1 0, 
q4 
1 
0,1 N1 
 Qual são as etapas de processamento para a 
palavra 0001110? 
 E o resultado para 010110? 
 E 0100100? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
AFD vs. AFND 
 Muitas vezes é mais fácil desenvolver um AFN do que 
um AFD 
 Exemplo: Um autômato para reconhecer a seguinte 
linguagem: 
 L = { p | p|p contém 1 na terceira posição em ordem 
reversa} 
 Solução determinística: requer um número grande de 
estados e transições 
 Solução não-determinística: simples, poucos estados, 
poucas transições 
 Exercício: Projete um AFD que reconheça L; depois 
projete um AFND que reconheça L 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
AFD que Reconhece L 
50 
q000 q100 q010 
0 
0 0 
q110 
0 
q001 q101 q011 
1 
1 
q111 
1 
1 
1 
0 1 1 0 0 0 
1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
AFND que Reconhece L 
51 
q1 q2 q3 
0,1 
1 0, 1 
q4 
0,1 
N2 
 Quais características AFNDs permitiram a 
simplificação do diagrama de estados? 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de AFND 
 ∑ = ∑∪ , 2Q é conjunto das partes de Q 
 Um autômato finito não-determinísticoé 
representado pela quintupla (Q, ∑, , q0, F), 
onde 
1. Q é um conjunto finito de estados 
2. ∑ é o alfabeto 
3. : Q ∑ 2Q, é uma função de transição 
4. 𝑞0 ∈ 𝑄 é o estado inicial 
5. 𝐹 Q é o conjunto de estados finais 
 52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 A descrição formal de N1 é (Q, ∑, , q0, F), 
onde: 
1. Q = {q1, q2, q3, q4} 
2. ∑ = {0, 1} 
3. é dado pela tabela a dir.: 
4. q1 é o estado inicial 
5. F = {q4} 
 
53 
q1 q2 q3 
0,1 
1 0, q4 
1 
0,1 N1 
q1 
q2 
q3 
q4 
{q1} {q1,q2} 
0 1 e 
{q3} {q3} 
 {q3} 
{q4} {q4} 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição Formal de Computação 
de Autômatos Finitos Não-
Determinísticos 
 Seja M = (Q, ∑, , q0, F) um AFND e p uma 
palavra sobre o alfabeto ∑. Então M aceita p se 
podemos escrever p como 𝑦1𝑦2…𝑦𝑛, onde cada 
𝑦𝑖 é um membro de ∑ e existe uma sequência 
de estados r0, r1, ..., rn em Q satisfazendo as três 
condições seguintes: 
1. r0 = q0, 
2. ri+1 ∈ (ri, yi+1) para i=0,...,n, e 
3. 𝑟𝑛 ∈ 𝐹 
54 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício de Fixação (1) 
 Projete um AFND com um alfabeto {0} que 
aceite todas palavras com o seguinte formato: 
• 0k onde k é múltiplo de 2 ou três 
• Dica: Projete um dois autômatos, um que 
reconheça 0k quando k é múltiplo de 2 e outro 
quando k é múltiplo de três; conecte-os usando 
transições 𝜀 
 
55 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício de Fixação (1) 
56 
𝜀 
𝜀 
0 
0 
0 
0 
0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (2) 
 Apresente o diagrama de estados de um AFND 
que reconheça a seguinte linguagem: L = {p | 
p não contém abb como subpalavra}. O 
alfabeto de entrada é ∑ = {a,b} e o AFND deve 
conter no máximo 3 estados 
57 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (2) 
58 
q0 q1 q2 
b 
a 
a 
a 
b 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
 Autômatos finitos são popularmente usados 
para descrever computadores com memória 
limitada como diversos dispositivos 
eletrônicos. Entretanto, esta não é a única 
aplicação de autômatos finitos. Outra 
aplicação popular é a busca de palavras-chave 
(keywords) em um texto. Projete AFND que 
reconheça as palavras Church e Turing em um 
texto 
59 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (3) 
60 
q0 
q2 q3 q4 q5 q6 
C 
h u r c 
q7 
h 
∑ 
q2 q3 q4 q5 q6 
u r i n 
q7 
g 
∑ 
∑ 
T 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre Máquinas 
61 
 Duas máquinas são ditas equivalentes se elas 
reconhecem a mesma linguagem. 
 Em outras palavras, máquinas equivalentes 
possuem o mesmo poder de expressão, ou em 
outras palavras, o mesmo poder computacional 
 Note a diferência entre poder de computação e 
desempenho computacional – uma máquina com um 
número arbitrário de processadores paralelos terá, 
possivelmente, melhor desempenho que uma 
máquina que possui apenas um processador; 
entretanto, estas máquinas podem ter o mesmo 
poder computacional 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre AFD e AFNDs 
 Teorema: Todo autômato finito não-
determinístico tem um autômato finito 
determinístico equivalente 
 Prova por construção 
• Demonstrar como construir um AFD a partir de um 
AFND 
• Intuição: Dado um AFND de k estados, construir um 
AFD com 2k estados (um estado para subconjunto de 
estados do AFND). Definir as funções de transições, 
estado final e inicial com especial atenção à palavra 
vazia 
 62 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
63 
1 
2 3 a, b 
a 
b 
a 
 Vamos construir um AFD equivalente ao AFND 
acima para ilustrar os passos da prova 
 N={{1,2,3}, {a,b},𝛿, 1,{1}} 
 
 
N 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando o 
Conjunto de Estados 
 Dado um AFND N = (Q, ∑, , q0, F), construa 
um AFD M = (Q’, ∑, ’, q0, F’) da seguinte 
maneira: 
1. Q’ = 2Q. 
• O conjunto Q’ é dado pelo conjunto das partes 
de Q 
 Q = {1,2,3}, portanto 
 Q’ = 2Q ={∅,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, 
{1,2,3}} 
 
 
64 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando o Estado Final 
2. F ’ = 𝑅 ∈ 𝑄′|R contém um estado final de N} 
• M aceita a entrada se, ao final da palavra de 
entrada, uma das possíveis ramificações de 
processamento que N pode estar é um estado 
final 
• F = {1} 
• Q’ = 2Q ={∅,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} 
• F’ = {{1}, {1,2}, {1,3}, {1,2,3}} 
 
 
 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lidando com Transições Vazias 
 Dado um estado 𝑅 ∈ 𝑄′, defina 
E(𝑅) = {q | q pode ser alcançado partindo de R e 
atravessando 0 ou mais transições com 
• Em outras palavras, E(R) é a coleção de 
estados que pode ser alcançada de R 
através de setas com , incluindo os 
membros de R 
66 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lidando com Transições Vazias 
 E(1) = {1,2,3,4} 
67 
1 
2 
3 
 
4 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando o Estado Inicial 
3. q0’ = E({q0}) 
 Portanto, temos q0’ = {1,3} 
 
68 
1 
2 3 a, b 
a 
b 
a N 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando a 
Função de Transição 
 Primeiramente sem considerar transições vazias 
4. Para todo 𝑅 ∈ 𝑄′ e 𝑎 ∈ faça 
𝛿′ 𝑅, 𝑎 = 𝛿 𝑟, 𝑎
𝑟∈𝑅
 
• Cada estado de R de M corresponde a um conjunto 
de estados de N (por isso, 𝑟 ∈ 𝑅). Além disso, como 
cada transição de estados leva a um conjunto de 
estados, nós usamos a união de todos estes 
conjuntos 
 
69 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 
 
70 
1 
2 3 a, b 
a 
b 
a 
{1,2} {2,3} 
 𝛿′ *1,2+, 𝑎 = 𝛿 𝑟, 𝑎 = *2,3+𝑟∈𝑅 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando a 
Função de Transição 
 Considerando transições vazias temos: 
4. Função de transição: Para todo 𝑅 ∈ 𝑄′ e 
𝑎 ∈ faça 
𝛿′ 𝑅, 𝑎 = 𝐸(𝛿 𝑟, 𝑎 )
𝑟∈𝑅
 
 
 
 
71 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
 𝛿′ *1+, 𝑎 = {2,3} 
72 
{1} {2} 
a 
{3} 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo AFND -> AFD 
73 
1 
2 3 a, b 
a 
b 
a 
N4={{1,2,3}, {a,b},𝛿, 1,{1}} 
D4={Q′, ∑, 𝛿′, q0, F′} 
 Q’ = 2Q ={∅,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} 
 q0 ’ = E(q0) = {1,3} 
 F’ = *𝑅 ∈ 𝑄′|R contém um estado final de N} = 
 = {{1}, {1,2}, {1,3}, {1,2,3}} 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo AFND -> AFD (2) 
 𝛿′({2}, a) = {2,3} 
 𝛿′({2}, b) = {3} 
 𝛿′({1}, a) = ∅ 
 𝛿′({1,2}, a) = {2,3} 
 
 
 
74 
1 
2 3 a, b 
a 
b 
a 
N4={{1,2,3}, {a,b},𝛿, 1,{1}} 
D4={Q′, ∑, 𝛿′, q0, F′} 
E assim por diante… 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo AFND -> AFD (3) 
75 
∅ {1} {2} {1,2} 
D4 
{3} {1,3} {2,3} 
{1,2
,3} 
a,b a 
b 
b 
a 
b 
b 
a 
b 
a,b 
a 
b 
a 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Simplificação – Eliminação de 
Estados sem Setas Incidentes 
76 
∅ {1} {2} {1,2} 
D4 
{3} {1,3} {2,3} 
{1,2
,3} 
a,b a 
b 
b 
a 
b 
b 
a 
b 
a,b 
a 
b 
a 
X X 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
AFD Simplificado 
77 
∅ {2} 
D4 
{3} {1,3} {2,3} 
{1,2
,3} 
a,b 
b 
a 
b 
b 
a 
b 
a 
b 
a 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício de Fixação 
 Construa um AFD que seja equivalente ao AFND 
N representado abaixo. Note que o alfabeto de N 
é ∑ = {a,b}. O AFD construído não deverá conter 
estados desnecessários. 
 
78 
79 
{q0} {} {q2} {q1} 
{q0,q2} {q0,q1} {q0,q1,q2} {q1,q2} 
a 
b a 
b 
b 
a 
b 
a 
b 
b 
a 
a 
b 
Resposta 
a 
a,b 
Resposta: Simplificado 
80 
{} {q2} {q1} 
{q0,q1} {q0,q1,q2} 
a 
b 
b 
a 
b 
a 
b 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definição: Linguagem Regular 
 Uma linguagem é chamada de linguagem 
regular se algum autômato finito 
(determinístico ou não-determinístico) a 
reconhece 
81 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Operações Regulares 
Operações sobre linguagens 
 Seja A e B duas linguagens. Temos três operações 
de particular interesse: 
• União: A∪B = {x| x ∈ 𝐴 𝑜𝑢 𝑦 ∈ 𝐵+ 
• Concatenação: AB = { xy | x ∈ 𝐴 𝑜𝑢 𝑥 ∈ 𝐵 } (mesma 
semântica que produto cartesiano) 
• Estrela: A* = {x1x2…xk| k >= 0 e cada xi ∈ 𝐴} 
 A classe de linguagens regulares é fechada em 
relação a estas operações 
• O resultado da aplicação destas operações sobre 
linguagens regulares, em qualquer sequência ou 
quantidade, é também um linguagem regular 
 82 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Expressões Regulares 
 Usa operações regulares para descrever 
linguagens 
• 0∗10∗= {p| p tem apenas um símbolo 1} 
• 0∑*0∪ 1∑*1 ∪0 ∪1 = {p| p inicia e 
termina com o mesmo símbolo} 
• (∑∑)* = {p| p tem comprimento par} 
• 1° = 
• * = 
 
83 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Expressões Regulares 
 Dizemos que R é uma expressão regular se R é: 
• Algum símbolo em ∑ 
• 
• 
• R1∪R2, onde R1 e R2 são expressões 
regulares 
• R1 ° R2, onde R1 e R2 são expressões 
regulares 
• R*, onde R é uma expressão regular 
 
84 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre Expressões 
Regulares e AFs 
 Teorema: Uma linguagem é regular sse 
alguma regular expressão a descreve 
85