02.3.LFA.LinguagensRegulares

Prévia do material em texto

DCC063 
 
Linguagens Formais 
e Autômatos 
Linguagens Regulares 
Equivalência entre AFD e AFN com e sem -
transições 
 Para um autômato finito com -transições (ou 
com movimento vazio) define-se o -fecho de 
um estado e como o conjunto de estados 
alcançáveis a partir de e utilizando-se somente 
-transições: 
 ε𝑓𝑒𝑐ℎ𝑜 𝑞 = {𝑝 ∈ 𝑄|𝛿 𝑞, ε ⊢∗ 𝑝, ε } 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
2 
Equivalência entre AFD e AFN com e sem -
transições 
 Algoritmo (ε𝑓 𝑞 significa ε𝑓𝑒𝑐ℎ𝑜 𝑞 ): 
 
ε𝑓 𝑞 ≔ 𝑞 ; 
𝐞𝐪𝐮𝐚𝐧𝐭𝐨 ∃𝛿 𝑝, ε → 𝑟 com 𝑝 ∈ ε𝑓 𝑞 𝐞 𝑟 ∉ ε𝑓 𝑞 𝐟𝐚ç𝐚 
 ε𝑓 𝑞 ≔ ε𝑓 𝑞 ∪ 𝑟 ; 
fim-equanto; 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
3 
 Exemplo: Determinar o -fecho de cada estado 
do autômato: 
 
 
 
 
 -fecho(e0) = {e0, e1, e2} 
 -fecho(e1) = {e1, e2} 
 -fecho(e2) = {e2} 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 0 1 2  
e0 e0 - - e1 
 e1 - e1 - e2 
* e2 - - e2 - 
e0 e1 e2 
2 0 
  
1 
4 
Equivalência de AFN e AFN com AFD (Construção 
de AFD a partir de um AFN) 
 Seja 𝑀 = 𝐾, Σ, Δ, 𝑠, 𝐹 um AFN. Devemos 
construir um AFD 𝑀′ = 𝐾′, Σ, 𝛿, 𝑠′, 𝐹′ 
equivalente a M da seguinte forma: 
 𝐾′ = 2𝐾 
 𝑠′ = 𝜀𝑓 𝑠 
 𝐹′ = 𝑄 ⊆ 𝐾′|𝑄 contém um estado final de 𝑀 
 e, para cada 𝑄 ⊆ 𝐾 e cada símbolo a ∈ Σ, definir: 
δ 𝑄, 𝑎 =∪ 𝜀𝑓 𝑝 |𝑝 ∈ 𝐾 e 𝑞, 𝑎 → 𝑝 ∈ ∆, para 𝑞 ∈ 𝑄 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
5 
Ideia do Algoritmo 
 
 
 
 
 
 
 
 Veja o exemplo a seguir 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 
 
a 
 
 
 
a 
 
 
 
a 
 
a 
 
a 
 
a 
Caso 1 
Caso 2 
6 
 Exemplo1: Transformar o AF abaixo em um AFD: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
7 
q1 q10 q2 
 
q3 q5 
q6 q4 
q7 q9 q8 
 
 
0 
1 
   0 
 
 
 
 Exemplo1. Transformar o AF abaixo em um AFD: 
 Calculo do -fecho para cada um dos 10 estados de A: 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
8 
Estado -fecho 
q1
 
q2 
q3 
q4 
q5 
q1 
q2 
q4 
q3 
q5 
Estado -fecho 
q6 
q7 
q8 
q9 
q10 
q6 
q9 
q8 
q10 
q7 
,q2 ,q8 
,q3 ,q4 
,q7 
,q7 
,q2 
,q9 
q3 ,q4 ,q9 
,q8 
q2 
,q8 
,q8 
q2 
q3 ,q4 
,q9 
,q9 
,q9 
,q3 ,q4 
,q3 ,q4 
 Exemplo1: Transformar o AF abaixo em um AFD: 
 Determinar o novo estado inicial s1: 
𝑠1 = 𝜀𝑓 𝑞1 = 𝑞1, 𝑞2, 𝑞3, 𝑞4, 𝑞8, 𝑞9 
 Quais estados são atingidos, usando apenas 
transições não 𝜀, pelos estados que estão em 𝜀𝑓 𝑞1 . 
 
 
 
 Estas serão as transições partindo de s1. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
9 
 0 1 
s1 q5, q10 q6 
0 
s1 
q5,10 
q6 
1 
 Exemplo1: Transformar o AF abaixo em um AFD: 
 Novo estado s2: 
𝑠2 = 𝜀𝑓 𝑞5 ∪ 𝜀𝑓 𝑞10 = 𝑞2, 𝑞3, 𝑞4, 𝑞5, 𝑞8, 𝑞9, 𝑞10 
 Transições para s2. 
 
 
 
 Estas serão as transições partindo de s2. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
10 
 0 1 
s2 q5, q10 q6 
0 
s2 
q5,10 
q6 
1 
 Exemplo1: Transformar o AF abaixo em um AFD: 
 Novo estado s3: 
𝑠3 = 𝜀𝑓 𝑞6 = 𝑞2, 𝑞3, 𝑞4, 𝑞6, 𝑞7, 𝑞8, 𝑞9 
 Transições para s3. 
 
 
 
 Estas serão as transições partindo de s3. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
11 
 0 1 
s3 q5, q10 q6 
0 
s3 
q5,10 
q6 
1 
 Exemplo1: Transformar o AF abaixo em um AFD: 
 Foram analisados todos os conjuntos de estados 
atingidos por transições não . Logo, podemos 
construir o AFD resultante. 
 
 
 
 
 
 Os novos estados que contêm o estado final q10 
também serão finais. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
12 
 0 1 
 s1 s2 s3 
* s2 s2 s2 
s3 s2 s2 
0 
s1 
1 
s2 
s3 
0 
0 1 
1 
 Exemplo2: Transformar o AF abaixo em um AFD: 
 
 
 
 
 Cálculo do fecho: 
 f(e0) = {e0, e1, e2} 
 f(e1) = {e1, e2} 
 f(e2) = {e2} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 0 1 2  
e0 e0 - - e1 
 e1 - e1 - e2 
* e2 - - e2 - 
13 
e0 e1 e2 
2 0 
  
1 
 Exemplo2: Transformar o AF abaixo em um AFD: 
 Determinar o novo estado inicial s1: 
𝑠1 = 𝜀𝑓 𝑒0 = 𝑒0, 𝑒1, 𝑒2 
 Quais estados são atingidos, usando apenas 
transições não 𝜀, pelos estados que estão em 𝜀𝑓 𝑒0 . 
 
 
 
 
 Estas serão as transições partindo de s1. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
14 
 0 1 2 
s1 e0 e1 e2 
0 
s1 
e0 
e1 
1 
e2 
2 
 Exemplo2: Transformar o AF abaixo em um AFD: 
 Novo estado s2: 
𝑠2 = 𝜀𝑓 𝑒1 = 𝑒1, 𝑒2 
 Transições para s2. 
 
 
 
 Estas serão as transições partindo de s2. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
15 
1 
s2 
e1 
e2 
2 
 0 1 2 
s2 – e1 e2 
 Exemplo2: Transformar o AF abaixo em um AFD: 
 Novo estado s3: 
𝑠3 = 𝜀𝑓 𝑒2 = 𝑒2 
 Transições para s3. 
 
 
 
 Estas serão as transições partindo de s3. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
16 
s3 e2 
2 0 1 2 
s3 – – e2 
 Exemplo2: Transformar o AF abaixo em um AFD 
 Substituir cada ei por seu respectivo f(ei), Assim: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
17 
 0 1 2 
s1 e0 e1 e2 
 0 1 2 
s2 – e1 e2 
 0 1 2 
s3 – – e2 
 0 1 2 
s1 f(e0) f(e1) f(e2) 
 0 1 2 
s1 s1 s2 s3 
 0 1 2 
s2 – f(e1) f(e2) 
 0 1 2 
s2 – – f(e2) 
 0 1 2 
s2 – s2 s3 
 0 1 2 
s3 – – s3 
 Exemplo2: Transformar o AF abaixo em um AFD 
 Finalmente, obtém-se o AFD: 
 
 
 
 
 
 
 Como o e2 está no fecho de s1, s2 e s3; estes também 
serão estados finais. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
18 
  0 1 2 
* s1 s1 s2 s3 
* s2 – s2 s3 
* s3 – – s3 
s3 
2 0 1 
s2 s1 
1 
2 
2 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 Exemplo3: Transformar AFN  AFD, 
considerando o AFN abaixo: 
 
 b b 
 
  
 
b 
 
 
q0 q1 q2 q3 q4 q5 
a 
  a b  
q0 - q1 q1 
 q1 - - q2, q5 
 q2 q4 q3 - 
 q3 - q4 - 
 q4 - - q2, q5 
* q5 - - - 
 Tabela 
19 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estado -fecho 
q0 q0, q1, q2, q5 
q1 q1, q2, q5 
q2 q2 
q3 q3 
q4 q4, q2, q5 
q5 q5 
20 
 Exemplo3: Transformar AFN  AFD 
 fecho: 
 Exemplo3: Transformar AFN  AFD: 
 Determinar o novo estado inicial s1: 
𝑠1 = 𝜀𝑓 𝑞0 = 𝑞0, 𝑞1, 𝑞2, 𝑞5 
 Quais estados são atingidos, usando apenas 
transições não 𝜀, pelos estados que estão em 𝜀𝑓 𝑞0 . 
 
 
 
 Estas serão as transições partindo de s1. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
21 
 a b 
s1 q4 q1, q3 
 Exemplo3: Transformar AFN  AFD: 
 Novo estado s2: 
𝑠2 = 𝜀𝑓 𝑞1 ∪ 𝜀𝑓 𝑞3 = 𝑞1, 𝑞2, 𝑞3, 𝑞5 
 Transições para s2. 
 
 
 
 Estas serão as transições partindo de s2. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
22 
 a b 
s2 q4 q3, q4 
 Exemplo3:Transformar AFN  AFD: 
 Novo estado s3: 
𝑠3 = 𝜀𝑓 𝑞4 = 𝑞2, 𝑞4, 𝑞5 
 Transições para s3. 
 
 
 
 Estas serão as transições partindo de s3. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
23 
 a b 
s3 q4 q3 
 Exemplo3: Transformar AFN  AFD: 
 Novo estado s4: 
𝑠4 = 𝜀𝑓 𝑞3 ∪ 𝜀𝑓 𝑞4 = 𝑞2, 𝑞3, 𝑞4, 𝑞5 
 Transições para s4. 
 
 
 
 Estas serão as transições partindo de s4. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
24 
 a b 
s4 q4 q3, q4 
 Exemplo3: Transformar AFN  AFD: 
 Novo estado s5: 
𝑠5 = 𝜀𝑓 𝑞3 = 𝑞3 
 Transições para s4. 
 
 
 
 Estas serão as transições partindo de s5. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
25 
 a b 
s5 – q4 
 Exemplo3: Transformar AFN  AFD: 
 Foram analisados todos os conjuntos de estados 
atingidos por transições não . 
 Juntando as tabelas 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
26 
 a b 
s1 q4 q1, q3 
s2 q4 q3, q4 
s3 q4 q3 
s4 q4 q3, q4 
s5 – q4 
𝑠1 = 𝜀𝑓 𝑞0 
𝑠2 = 𝜀𝑓 𝑞1 ∪ 𝜀𝑓 𝑞3 
𝑠3 = 𝜀𝑓 𝑞4 
𝑠4 = 𝜀𝑓 𝑞3 ∪ 𝜀𝑓 𝑞4 
𝑠5 = 𝜀𝑓 𝑞3 
 Definição de cada estado 
 Exemplo3: Transformar AFN  AFD: 
 AFD resultante: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
27 
 a b 
* s1 s3 s2 
* s2 s3 s4 
* s3 s3 s5 
* s4 s3 s4 
s5 – s3 
s4 s3 
b 
s1 
s2 
a 
b 
a b 
a 
s5 
b 
a 
b 
 Exemplo4: Transformar AFN  AFD: 
 
 
 
 
 Cálculo do fecho: 
 f(1) = {1, 3} 
 f(2) = {2} 
 f(3) = {3} 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
28 
1 
b 
a, b 
2 3 a 
 
a 
 Exemplo4: Transformar AFN  AFD: 
 Determinar o novo estado inicial s13: 
𝑠13 = 𝜀𝑓 1 = 1,3 
 Quais estados são atingidos, usando apenas 
transições não 𝜀, pelos estados que estão em 𝜀𝑓 1 . 
 
 
 
 Estas serão as transições partindo de s13. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
29 
 a b 
s13 1 2 
 Exemplo4: Transformar AFN  AFD: 
 Novo estado s2: 
𝑠2 = 𝜀𝑓 2 = 2 
 Transições para s2. 
 
 
 
 Estas serão as transições partindo de s2. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
30 
 a b 
s2 2, 3 3 
 Exemplo4: Transformar AFN  AFD: 
 Novo estado s23: 
𝑠23 = 𝜀𝑓 2 ∪ 𝜀𝑓 3 = 2,3 
 Transições para s23. 
 
 
 
 Estas serão as transições partindo de s23. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
31 
 a b 
s23 2, 3, 1 3 
 Exemplo4: Transformar AFN  AFD: 
 Novo estado s123: 
𝑠123 = 𝜀𝑓 1 ∪ 𝜀𝑓 2 ∪ 𝜀𝑓 3 = 1,2,3 
 Transições para s123. 
 
 
 
 Estas serão as transições partindo de s123. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
32 
 a b 
s123 2, 3, 1 2, 3 
 Exemplo4: Transformar AFN  AFD: 
 Novo estado s3: 
𝑠3 = 𝜀𝑓 3 = 3 
 Transições para s3. 
 
 
 
 Estas serão as transições partindo de s3. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
33 
 a b 
s3 1 – 
 Exemplo4: Transformar AFN  AFD: 
 Foram analisados todos os conjuntos de estados 
atingidos por transições não . 
 Juntando as tabelas 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
34 
 a b 
s13 1 2 
s2 2, 3 3 
s23 2, 3, 1 3 
s123 2, 3, 1 2, 3 
s3 1 – 
𝑠13 = 𝜀𝑓 1 
𝑠2 = 𝜀𝑓 2 
𝑠23 = 𝜀𝑓 2 ∪ 𝜀𝑓 3 
𝑠123 = 𝜀𝑓 1 ∪ 𝜀𝑓 2 ∪ 𝜀𝑓 3 
𝑠3 = 𝜀𝑓 3 
 Definição de cada estado 
 Exemplo4: Transformar AFN  AFD: 
 AFD resultante: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
35 
 a b 
* s13 s13 s2 
s2 s23 s3 
s23 s123 s3 
* s123 s123 s23 
s3 s13 – 
s13 b 
a 
s2 
a 
b s3 
s23 
s123 
a 
b 
a 
b 
a 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Minimização de Autômatos Finitos 
 Diz-se que um AF é mínimo se ele não possui 
estados inatingíveis ou mortos e se não existem 
estados equivalentes entre si; 
 Exceto pelos nomes dos estados, existe apenas 
uma máquina mínima para um dado problema 
de reconhecimento 
36 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Inatingíveis 
 Pode haver alguns estados no AF que nunca 
serão atingidos com nenhuma seqüência de 
símbolos a partir do estado inicial 
 Tais estados são chamados de estados 
inatingíveis. As linhas da tabela que 
correspondem a estados inatingíveis podem ser 
simplesmente removidas da tabela de transição 
para deixar a máquina com menos estados. 
37 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Inatingíveis 
 Algoritmo: Eliminação de Estados 
Inatingíveis 
 Entrada: Um Autômato Finito 
 M = (E, A, t, e0, F) 
 Saída: Um Autômato Finito sem estados 
Inatingíveis 
 M’ = (E’, A, t’, e0, F’) 
38 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Inatingíveis 
 Inicialize o conjunto de estados atingíveis E’ com o estado 
inicial e0. 
 Adicione, em E’, para cada estado e, presente no conjunto E’, 
todos os estados d que podem ser alcançados por uma 
transição a partir de e, ou seja, todos os estados d tal que t(e,x) 
= d para algum xA. 
 Se nenhum novo estado pode ser adicionado ao conjunto E’ 
com o uso destas regras, já foi obtido o conjunto de estados 
atingíveis. 
 Coloque em t’ todas as transições t(x,y)=z tal que x,zE’ e yA. 
Coloque em F’ todos os estados que pertencem 
simultaneamente a F e a E’. 
39 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Mortos 
 Um estado e de um AF é morto se ele não é final 
e se a partir dele não se pode atingir nenhum 
estado final. 
 Para eliminar os estados mortos de um AF M 
proceda como segue: 
Algoritmo: Eliminação de Estados Mortos 
 Entrada: Um AF M = (E, A, t, e0, F) 
 Saída: Um AF sem estados mortos M’ = (E’, A, t’, 
e0’, F) 
40 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Mortos 
 (1)Inicialize o conjunto de estados não-mortos E’ com os 
estados finais F de M. 
 (2)Para cada estado e em E’, adicione os estados de E que 
levam para e com uma transição de t para algum símbolo de 
entrada. Ou seja, adicione em E’ o conjunto {x| t(x,a) = e, eE’ 
e aA} 
 (3)Repita o passo (2) até que mais nenhum estado possa ser 
adicionado ao conjunto E’. 
 (4)Coloque em t’ todas as transições t(x,y) = z tal que x, zE’ e 
yA. Se e0E’ então faça e0’= e0; caso contrário, e0’ é um novo 
símbolo de estado e a linguagem reconhecida pelo autômato 
é vazia, uma vez que o estado inicial é morto. 
41 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Considere os estados de aceitação (finais) c e g. 
São estados que, uma vez atingidos, nunca se sai 
deles, desde que que se leia 0 ou 1. Esses dois 
estados são realmente necessários? 
42 
c 
0,1 
b 0 
a d 
g 
0 
1 
0 
1 0,1 f 
e 0 
1 
1 
0,1 
Não. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Quando o controle atinge os estados b ou f então: 
 se a cadeia termina, é rejeitada em ambos casos; 
 se a próxima entrada é 0, aceita com qualquer sufixo em 
ambos casos 
 se a próxima entrada é 1, rejeita com qualquer sufixo em 
ambos casos 
43 
b 0 
a d c,g 
0 1 
01 
0,1 
f 
e 0 
1 
1 
0,1 
Os estados b e f 
também podem ser 
unificados. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Intuitivamente, dois estados são equivalentes se 
todas as computações a partir deles são iguais 
44 
b,f 0 
a 
d 
c,g 
0 
0,1 
e 
0 
1 
1 
0,1 
1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Removendo o estado inatingível d e o estado 
morto e obtém-se o autômato: 
45 
b,f 0 
a c,g 
0 
0,1 
1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Dois estados e e d são equivalentes se e somente 
se as duas condições seguintes forem satisfeitas: 
 (a)Condição de compatibilidade: os estados e e d 
devem ser ambos finais ou ambos não-finais. 
 (b)Condição de propagação: para qualquer símbolo 
de entrada, os estados e e d devem levar a estados 
equivalentes. 
46 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 As condições (a) e (b) podem ser incorporadas 
em um teste geral de equivalência entre estados 
 O método é chamado método da separação, uma 
vez que seu objetivo é separar, ou particionar, o 
conjunto de estados em subconjuntos disjuntos, 
ou blocos, tal que estados não-equivalentes 
fiquem em blocos separados 
47 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 O método é ilustrado por sua aplicação no AF da 
tabela seguinte: 
 t a b 
e1 e6 e3 
 e2 e7 e3 
 e3 e1 e5 
 e4 e4 e6 
* e5 e7 e3 
* e6 e4 e1 
* e7 e4 e2 
48 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Os estados são inicialmente separados em dois 
blocos; um contendo os estados finais e outro 
contendo os estados não-finais 
 Para o exemplo, a partição inicial L0 é dada pela 
seguinte lista: 
 
 L0 = [{e1, e2, e3, e4},{e5, e6, e7}] 
 
 já que e1, e2, e3 e e4 são estados não finais e e5, e6 
e e7 são estados finais 
49 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Observe o que acontece aos estados no bloco {e1, 
e2, e3, e4} com entrada a: 
 Os estados e3 e e4 vão para estados contidos no 
primeiro bloco (e1 e e4 respectivamente) 
 enquanto os estados e1 e e2 vão para estados no 
segundo bloco (e6 e e7 respectivamente) 
 Isto significa que para qualquer estado no 
conjunto {e1, e2 } e qualquer estado em {e3, e4} 
os estados seguintes correspondendo a entrada 
a não serão equivalentes 
50 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Pode concluir que nenhum estado em {e1, e2} 
será equivalente a nenhum estado em {e3, e4}. 
Isto habilita a construção de uma nova partição: 
 L1 = [{e1, e2},{e3, e4},{e5, e6, e7}] 
 Agora se tentará encontrar um bloco em L1 e 
uma entrada tal que o bloco possa ser separado 
com respeito a entrada e uma nova partição seja 
assim obtida 
51 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Este processo deve ser repetido até que 
nenhuma nova separação seja possível. No 
exemplo, a continuação seria a seguinte: 
Separando {e3, e4} de L1 com respeito a a: 
 L2 = [{e1, e2},{e3},{e4},{e5, e6, e7}] 
Separando {e5, e6, e7} de L2 com respeito a a (ou 
b): 
 L3 = [{e1, e2},{e3},{e4},{e5},{e6, e7}] 
 
52 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 A partição L3 não pode ser mais separada. Para 
verificar isto, observe que todos os estados no 
bloco {e1, e2} vão para estados no bloco{e6, e7} 
com entrada a, e para o bloco {e3} com entrada b 
 Similarmente {e6, e7} vão para os blocos {e4 } e 
{e1, e2} com entrada a e b, respectivamente 
53 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Quando o procedimento termina, os estados 
dentro de um mesmo bloco são equivalentes. No 
exemplo, os estados e1 e e2 são equivalentes e os 
estados e6 e e7 também. 
 Os blocos da partição final podem ser usados 
para construir uma nova máquina, a qual é 
equivalente à original, porém sem possuir 
estados equivalentes. 
54 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Para o exemplo a máquina mínima resultante 
seria: 
 t a b t a b 
 {e1, e2} {e6, e7} {e3} e1 e5 e2 
 {e3} {e1, e2} {e5} e2 e1 e4 
 {e4} {e4} {e6, e7} ou e3 e3 e5 
* {e5} {e6, e7} {e3} * e4 e5 e2 
* {e6, e7} {e4} {e1, e2} * e5 e3 e1 
 
55 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estados Equivalentes 
 Ou em forma de diagrama de transição (com os 
estados renomeados): 
e1
a
e2
e5
b
a
b
e4
e3
a
b
a
a
b
b
56 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
57 
Estados Equivalentes 
 Exemplo 2: Achar e unificar os estados 
equivalentes do AFD abaixo 
0 
C B 0 A 
0 
D 
F E H G 
1 
1 
0 
1 
1 
0 
1 1 
0 0 
1 
0 
1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
58 
Estados Equivalentes 
 Exemplo 2: Pela condição de compatibilidade: 
𝐿0 = 𝐴, 𝐵, 𝐷, 𝐸, 𝐹, 𝐺, 𝐻 , 𝐶 
 Observe que os estados B, D, F e H possuem 
transições para C e os demais – A, E e G – não as 
possuem. Logo A, E e G não são equivalentes aos 
demais: 
𝐿1 = 𝐴, 𝐸, 𝐺 , 𝐵, 𝐷, 𝐹, 𝐻 , 𝐶 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
59 
Estados Equivalentes 
 Aplicando a condição de propagação. Observe que G 
fica no mesmo grupo enquanto A e E vão para 
outro: 
𝐿2 = 𝐴, 𝐸 , 𝐺 , 𝐵, 𝐷, 𝐹, 𝐻 , 𝐶 
 Aplicando a condição de propagação. B e H vão para 
C com 1 e com 0 para G. D e F vão com 1 para G e 0 
para C: 
𝐿3 = 𝐴, 𝐸 , 𝐺 , 𝐵, 𝐻 , , 𝐷, 𝐹 , 𝐶 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
60 
Estados Equivalentes 
 Não há como separar mais os conjuntos de estados 
usando a condição de propagação: 
C 
A,E 
1 
B,H 
0 0 
1 
0 
1 
0 
1 
D,F G 
0 1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Estado de Erro 
 Para não deixar transições indefinidas em M, 
pode-se substituir todas as indefinições por um 
estado de erro “ERRO” e adicionar este estado à 
tabela. Para cada símbolo de entrada o estado 
“ERRO” tem transição para si próprio. O estado 
de erro não deve jamais ser definido como 
estado final 
61 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
Autômato Finito Mínimo 
Algoritmo: Minimização de Autômato Finito 
Entrada: um Autômato Finito M = (E, A, t, e0, F). 
Saída: um AF mínimo M’ = (E’, A, t’, e0’, F’). 
1. Elimine os estados inatingíveis (ou inalcançáveis); 
2. Elimine os estados mortos; 
3. Adicione o estado de erro; 
4. Elimine os estados redundantes (equivalentes) 
62 
Equivalência entre ER’s e AF’s 
 Pode-se construir um ER a partir de qualquer AFD. 
Tal construção mostra que se uma linguagem é 
regular, então ela e descrita por uma ER. 
 O método deve ser aplicado para um AFNG 
(Autômato Finito Não-determinístico 
Generalizado). 
 Isto é, o AFD deve ser transformado num AFNG e 
este último numa ER. 
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
63 
Conversão AFD  AFNG 
 AFNG são simplesmente AFN nos quais as setas de 
transição podem ter quaisquer ER como rótulos; Sendo assim, o AFNG lê blocos de entrada (não 
apenas um símbolo de cada vez) e se move ao 
longo de uma transição entre 2 estados ao ler tal 
bloco o quol constitui uma cadeia descrita pela 
expressão regular sobre a seta. 
 Um AFNG é não-determinístico e, portanto, pode 
ter várias forma de processar a mesma entrada. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
64 
Conversão AFD  AFNG 
 Exemplo de AFNG 
 
 
 
 
 
 
 
 Uma transição rotulada ∅ nunca é utilizada. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
65 
qfim qini 
ab* 
∅ 
𝑏 
b* 
ab 
𝑎𝑎 ∗ 
𝑎𝑎 
𝑎𝑏|𝑏𝑎 
𝑎∗ 
Conversão AFD  AFNG 
 Será exigido que o AFNG tenha, por conveniência, 
o seguinte formato: 
 O estado inicial tem transições para todos os outros, 
mas nenhum chegando de qualquer outro; 
 Existe apenas um estado final ( do inicial), e ele tem 
transições chegando de todos os outros, mas nenhuma 
saindo para qualquer outro estado; 
 Com exceção dos estados inicial e final, uma transição 
sai de cada estado para todos os outros e para ele 
mesmo. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
66 
Conversão AFD  AFNG 
 É fácil fazer a conversão AFD  AFNG com este 
formato especial: 
 Adiciona-se um novo estado inicial com rótulo 𝜀 para 
o estado inicial antigo e um novo estado final com 
rótulo 𝜀 chegando dos antigos estados finais; 
 Se há múltiplas transições entre dois estados na 
mesma direção, substitui-se cada uma por uma única 
transição com rótulo sendo a união dos rótulos 
originais; 
 Finalmente, adiciona-se transições com rótulo ∅ entre 
estados que não tenham transições definidas. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
67 
Conversão AFD  AFNG 
 Definição Formal de AFNG. Um AFNG é uma 
5-tupla, 𝑄, Σ, 𝛿, 𝑞0, 𝑞𝑓 , onde: 
 𝑄: conjunto finito de estados; 
 Σ: alfabeto de entrada; 
 𝛿: 𝑄 − 𝑞𝑓 × 𝑄 − 𝑞0 → 𝑅 é a função de transição; 
 𝑞0: estado inicial; 
 𝑞𝑓: estado final. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
68 
Equivalência entre ER’s e AF’s 
 A conversão AFNG  ER é realizada removendo 
um estado de cada vez do AFNG segunda a regra 
abaixo (𝑝𝑟 ⟹ estado a ser removido; 𝑟𝑖 ⟹ 𝐸𝑅) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
69 
qi 
pr 
qj 
𝑟2 
𝑟3 𝑟1 
𝑟4 
⟹ qi qj 
𝑟1 
As remoções dos estados 
acabarão no momento em que 
sobrarem apenas dois 
estados: inicial e final. 
𝑟2
∗ 𝑟4 𝑟3 | 
Equivalência entre ER’s e AF’s 
 Exemplo 1. Converter o AFD abaixo num ER. 
 Transformação do AFD em um AFNG 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
70 
1 
𝑏 2 
𝑎 
𝑏 
𝑎 
⟹ 
𝐴𝐹𝑁𝐺 
𝑎|𝑏 
𝜀 f 
1 
𝑎 
𝑏 
2 
s 𝜀 
Equivalência entre ER’s e AF’s 
 Exemplo 1. Converter o AFD abaixo num ER. 
 Remoção do estado 2 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
71 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 2 
𝑎|𝑏 
𝜀 f 
1 
𝑎 
𝑏 
2 
s 𝜀 
f 
1 
𝑎 
𝑏 𝑎|𝑏 ∗ 
s 𝜀 
Equivalência entre ER’s e AF’s 
 Exemplo 1. Converter o AFD abaixo num ER. 
 Remoção do estado 1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
72 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
f 
1 
𝑎 
𝑏 𝑎|𝑏 ∗ 
s 𝜀 
f 
𝑎∗𝑏 𝑎|𝑏 ∗ 
s 
Como restaram apenas os 
estados inicial e final, o rótulo da 
transição entre eles é a ER do 
AFD: 𝑎∗𝑏 𝑎|𝑏 ∗ 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
73 
3 
2 1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Transformação do AFD em um AFNG 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
74 
3 
2 1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 ⟹ 
𝐴𝐹𝑁𝐺 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = s e qj = 3) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
75 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
𝑏 
3 
𝑏 
f 
2 s 
𝜀 
𝜀 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = s e qj = 2) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
76 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
3 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝑏 
𝑎 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = 2 e qj = 3) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
77 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
3 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = 3 e qj = 2) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
78 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
3 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = 2 e qj = 2) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
79 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 1 (Trata qi = 3 e qj = 3) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
80 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 1 
3 
1 
𝑎 
𝑎 
𝑏 
𝑏 
𝑎 
𝑏 
f 
2 s 
𝜀 
𝜀 
𝜀 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
𝑏𝑏 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 2 (Trata qi = s e qj = f) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
81 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 2 
f s 
𝑎 𝑎𝑎|𝑏 ∗ 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
𝑏𝑏 
3 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 2 (Trata qi = s e qj = 3) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
82 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 2 
f s 
𝑎 𝑎𝑎|𝑏 ∗ 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
𝑏𝑏 
3 𝑎 𝑎𝑎|𝑏 ∗ab|b 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 2 (Trata qi = 3 e qj = f) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
83 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 2 
f s 
𝑎 𝑎𝑎|𝑏 ∗ 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎𝑏𝑏 
3 𝑎 𝑎𝑎|𝑏 ∗ab|b 
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗|𝜀 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 2 (Trata qi = 3 e qj = 3) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
84 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 2 
f s 
𝑎 𝑎𝑎|𝑏 ∗ 
3 
𝑎𝑎|𝑏 
f 
2 s 
𝜀 
𝜀 
𝑎 
𝑏 
𝑎𝑏 
𝑏𝑎|𝑎 
𝑏𝑏 
3 𝑎 𝑎𝑎|𝑏 ∗ab|b 
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗|𝜀 
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗𝑎𝑏|𝑏𝑏 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Remoção do estado 3 (Trata qi = s e qj = f) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
85 
⟹ 
𝑟𝑒𝑚𝑜𝑣𝑒 3 
f s 
𝑎 𝑎𝑎|𝑏 ∗ 
3 𝑎 𝑎𝑎|𝑏 ∗𝑎𝑏|𝑏 
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗|𝜀 
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗𝑎𝑏|𝑏𝑏 
f s 
Equivalência entre ER’s e AF’s 
 Exemplo 2. Dado o AFD de 3 estados, determinar a 
ER equivalente. 
 Obtém-se, finalmente, a ER do AFD 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
86 
𝑎 𝑎𝑎|𝑏 ∗𝑎𝑏|𝑏 𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗𝑎𝑏|𝑏𝑏
∗
𝑏𝑎|𝑎 𝑎𝑎|𝑏 ∗|𝜀 |𝑎 𝑎𝑎|𝑏 ∗ 
f s 
Equivalência entre ER’s e AF’s 
 Exercícios. Dado o AFD abaixo, determinar a ER 
equivalente. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
87 
A2 
q2 
1 
0 0 
1 
q1 q0 
q3 
0 0 
1 
1 
Equivalência entre ER’s e AF’s 
 Exercícios. Dados os AFDs abaixo, determinar a 
ER equivalente. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
88 
q1 q2 
b 
a 
q0 
qf 
a 
a 
a b 
b 
b 
q1 
1 
0 
0 1 
0 
q2 q3 
2 
3 
q1 
0 
0 1 
q2 1 
Equivalência entre ER’s e AF’s 
 Exercícios. Dados os AFDs abaixo, determinar a 
ER equivalente. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
89 
q2 
b 
b a 
a 
4 
s 
r1 q1 
r2 
a 
a b 
b 
b a 
q0 
a 
a 
b 
q2 q1 
