Aulas5-8Automatos
85 pág.

Aulas5-8Automatos


DisciplinaTeoria da Computação545 materiais16.691 seguidores
Pré-visualização4 páginas
é 
representado pela quintupla (Q, \u2211, , q0, F), 
onde 
1. Q é um conjunto finito de estados 
2. \u2211 é o alfabeto 
3. : Q \u2211 2Q, é uma função de transição 
4. \ud835\udc5e0 \u2208 \ud835\udc44 é o estado inicial 
5. \ud835\udc39 Q é o conjunto de estados finais 
 52 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
\uf0a7 A descrição formal de N1 é (Q, \u2211, , q0, F), 
onde: 
1. Q = {q1, q2, q3, q4} 
2. \u2211 = {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 
\uf0a7 Seja M = (Q, \u2211, , q0, F) um AFND e p uma 
palavra sobre o alfabeto \u2211. Então M aceita p se 
podemos escrever p como \ud835\udc661\ud835\udc662\u2026\ud835\udc66\ud835\udc5b, onde cada 
\ud835\udc66\ud835\udc56 é um membro de \u2211 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 \u2208 (ri, yi+1) para i=0,...,n, e 
3. \ud835\udc5f\ud835\udc5b \u2208 \ud835\udc39 
54 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício de Fixação (1) 
\uf0a7 Projete um AFND com um alfabeto {0} que 
aceite todas palavras com o seguinte formato: 
\u2022 0k onde k é múltiplo de 2 ou três 
\u2022 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 \ud835\udf00 
 
55 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício de Fixação (1) 
56 
\ud835\udf00 
\ud835\udf00 
0 
0 
0 
0 
0 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercícios de Fixação (2) 
\uf0a7 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 é \u2211 = {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) 
\uf0a7 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 
\u2211 
q2 q3 q4 q5 q6 
u r i n 
q7 
g 
\u2211 
\u2211 
T 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Equivalência entre Máquinas 
61 
\uf0a7 Duas máquinas são ditas equivalentes se elas 
reconhecem a mesma linguagem. 
\uf0a7 Em outras palavras, máquinas equivalentes 
possuem o mesmo poder de expressão, ou em 
outras palavras, o mesmo poder computacional 
\uf0a7 Note a diferência entre poder de computação e 
desempenho computacional \u2013 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 
\uf0a7 Teorema: Todo autômato finito não-
determinístico tem um autômato finito 
determinístico equivalente 
\uf0a7 Prova por construção 
\u2022 Demonstrar como construir um AFD a partir de um 
AFND 
\u2022 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 
\uf0a7 Vamos construir um AFD equivalente ao AFND 
acima para ilustrar os passos da prova 
\uf0a7 N={{1,2,3}, {a,b},\ud835\udeff, 1,{1}} 
 
 
N 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando o 
Conjunto de Estados 
\uf0a7 Dado um AFND N = (Q, \u2211, , q0, F), construa 
um AFD M = (Q\u2019, \u2211, \u2019, q0, F\u2019) da seguinte 
maneira: 
1. Q\u2019 = 2Q. 
\u2022 O conjunto Q\u2019 é dado pelo conjunto das partes 
de Q 
\uf0a7 Q = {1,2,3}, portanto 
\uf0a7 Q\u2019 = 2Q ={\u2205,{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 \u2019 = \ud835\udc45 \u2208 \ud835\udc44\u2032|R contém um estado final de N} 
\u2022 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 
\u2022 F = {1} 
\u2022 Q\u2019 = 2Q ={\u2205,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} 
\u2022 F\u2019 = {{1}, {1,2}, {1,3}, {1,2,3}} 
 
 
 
65 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Lidando com Transições Vazias 
\uf0a7 Dado um estado \ud835\udc45 \u2208 \ud835\udc44\u2032, defina 
E(\ud835\udc45) = {q | q pode ser alcançado partindo de R e 
atravessando 0 ou mais transições com 
\u2022 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 
\uf0a7 E(1) = {1,2,3,4} 
67 
1 
2 
3 
 
4 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando o Estado Inicial 
3. q0\u2019 = E({q0}) 
\uf0a7 Portanto, temos q0\u2019 = {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 
\uf0a7 Primeiramente sem considerar transições vazias 
4. Para todo \ud835\udc45 \u2208 \ud835\udc44\u2032 e \ud835\udc4e \u2208 faça 
\ud835\udeff\u2032 \ud835\udc45, \ud835\udc4e = \ud835\udeff \ud835\udc5f, \ud835\udc4e
\ud835\udc5f\u2208\ud835\udc45
 
\u2022 Cada estado de R de M corresponde a um conjunto 
de estados de N (por isso, \ud835\udc5f \u2208 \ud835\udc45). 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} 
\uf0a7 \ud835\udeff\u2032 *1,2+, \ud835\udc4e = \ud835\udeff \ud835\udc5f, \ud835\udc4e = *2,3+\ud835\udc5f\u2208\ud835\udc45 
a 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Determinando a 
Função de Transição 
\uf0a7 Considerando transições vazias temos: 
4. Função de transição: Para todo \ud835\udc45 \u2208 \ud835\udc44\u2032 e 
\ud835\udc4e \u2208 faça 
\ud835\udeff\u2032 \ud835\udc45, \ud835\udc4e = \ud835\udc38(\ud835\udeff \ud835\udc5f, \ud835\udc4e )
\ud835\udc5f\u2208\ud835\udc45
 
 
 
 
71 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
\uf0a7 \ud835\udeff\u2032 *1+, \ud835\udc4e = {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},\ud835\udeff, 1,{1}} 
D4={Q\u2032, \u2211, \ud835\udeff\u2032, q0, F\u2032} 
\uf0a7 Q\u2019 = 2Q ={\u2205,{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} 
\uf0a7 q0 \u2019 = E(q0) = {1,3} 
\uf0a7 F\u2019 = *\ud835\udc45 \u2208 \ud835\udc44\u2032|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) 
\uf0a7 \ud835\udeff\u2032({2}, a) = {2,3} 
\uf0a7 \ud835\udeff\u2032({2}, b) = {3} 
\uf0a7 \ud835\udeff\u2032({1}, a) = \u2205 
\uf0a7 \ud835\udeff\u2032({1,2}, a) = {2,3} 
 
 
 
74 
1 
2 3 a, b 
a 
b 
a 
N4={{1,2,3}, {a,b},\ud835\udeff, 1,{1}} 
D4={Q\u2032, \u2211, \ud835\udeff\u2032, q0, F\u2032} 
E assim por diante\u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo AFND -> AFD (3) 
75 
\u2205 {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 \u2013 Eliminação de 
Estados sem Setas Incidentes 
76 
\u2205 {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 
\u2205 {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 
\uf0a7 Construa um AFD que seja equivalente ao AFND 
N representado abaixo. Note que o alfabeto de N 
é \u2211 = {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 
\uf0a7 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 
\uf0a7