02.2.LFA.LinguagensRegulares

Prévia do material em texto

DCC013 
 
Linguagens Formais 
e Autômatos 
Linguagens Regulares 
 Definição: Autômato Finito não 
Determinístico com Movimentos vazios (com 
-transição), AFND ou AF. Um AF é uma 
quíntupla 𝑀 = Σ,𝑄, 𝛿, 𝑞0, 𝐹 , onde: 
 Σ: alfabeto de símbolos de entrada; 
𝑄 ≠ ∅: conjunto finito de estados; 
 𝛿: função programa ou função de transição 
 𝛿: 𝑄 × Σ ∪ 𝜀 → 2 𝑄 
 𝑞0 ∈ 𝑄: estado inicial; 
 F ⊂ 𝑄: conjunto de estados finais. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
2 
 Portanto, os componentes do AF são os 
mesmos do AFND, com exceção da função 
programa: 
 
 
 
 
 
 Pode existir apenas a -transição, isto é n = 0; 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
3 
p 
p2 p3 
 
p1 
a1 an 
⋯ 
 O processamento de uma transição para uma 
entrada vazia também é não-determinística. 
 O processamento dos AF é similar ao dos AFND. 
 Assim, um AFND, ao processar uma entrada 
vazia, assume simultaneamente os estados de 
origem e destino da transição 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
4 
 Exemplo: 𝐴𝐹𝜀 M8 = 𝑎, 𝑏 , 𝑞0, 𝑞𝑓 , 𝛿8, 𝑞0, 𝑞𝑓 : 
 
 
 
 
 
 M8 reconhece a linguagem: 
 L(M8) = {w | qualquer símbolo a antecede qualquer 
símbolo b}. 
 𝐿 8 = 𝑎𝑛𝑏𝑚|𝑚 ∈ ℤ, 𝑛 ∈ ℤ,𝑚 ≥ 0, 𝑛 ≥ 0 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
5 
8 a b  
q0 {q0} – {qf} 
qf – {qf} – * 
q0 
 
a b 
qf 
8 
 Computação determinística e não determinística 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
6 
Aceita ou rejeita Aceita 
Rejeita 
 Exemplo: AFND 
 𝑁1 = 𝑎, 𝑏 , 𝑞0, 𝑞1 , 𝛿𝑁1, 𝑞0, 𝑞1 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
7 
 𝐿 𝑁1 = 𝑢𝑣|𝑢 ∈ 𝑎 ∗, 𝑣 ∈ 𝑏 ∗ 
 𝐿 𝑁1 = 𝑎 ∗ 𝑏 ∗ 
q0 q1 
a 
 
b 
 Exemplo: AFND 
 𝑁2 = 𝑎, 𝑏, 𝑐 , 𝑞0, 𝑞1, 𝑞2, 𝑞3 , 𝛿𝑁2, 𝑞0, 𝑞3 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
8 
 𝐿 𝑁2 = 𝑎𝑖𝑏𝑗𝑐𝑘𝑎𝑙|𝑖, 𝑗, 𝑘, 𝑙 ∈ ℵ 
q0 
b c 
q3 q1 
a 
 
q2 
  
a 
 Exemplo: AFND 
 𝑁3 = 𝑑,+,−, . , 𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4 , 𝛿𝑁3, 𝑞0, 𝑞4 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
9 
𝐿 𝑁3 = 𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑒𝑚 𝑝𝑜𝑛𝑡𝑜 𝑓𝑙𝑢𝑡𝑢𝑎𝑛𝑡𝑒 𝑐𝑜𝑚/𝑠𝑒𝑚 𝑠𝑖𝑛𝑎𝑙 
q0 
- q4 q1 
 
d 
d + 
q2 
q3 
d 
d 
. 
. 
d 
 Exemplo: AFND 
 𝑁4 = 𝑑,+,−, . , 𝐸 , 𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4, 𝑞5, 𝑞6, 𝑞7 , 𝛿𝑁4, 𝑞0, 𝑞4, 𝑞7 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
10 
𝐿 𝑁4 =
𝑛ú𝑚𝑒𝑟𝑜𝑠 𝑒𝑚 𝑝𝑜𝑛𝑡𝑜 𝑓𝑙𝑢𝑡𝑢𝑎𝑛𝑡𝑒 𝑐𝑜𝑚/𝑠𝑒𝑚 𝑠𝑖𝑛𝑎𝑙
𝑒𝑚 𝑛𝑜𝑡𝑎çã𝑜 𝑐𝑖𝑒𝑛𝑡í𝑓𝑖𝑐𝑎
 
q0 
- q4 q1 
 
d 
d 
+ q2 
q3 
d 
d 
. 
. 
d 
q7 
d 
q5 q6 
d 
+ 
 
E 
- 
 Exemplo: AFND 
 𝑁5 = 0 , 𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4, 𝑞5 , 𝛿𝑁5, 𝑞0, 𝑞1, 𝑞3 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
11 
𝐿 𝑁5 = 0𝑘|𝑘 mod 2 = 0 ou 𝑘 mod 3 = 0 
q0 
q3 
q2 q1 
q5 
q4 
0 
0 
 
 
0 
0 
0 
 Exemplo: AFND M9 = ({0,1}, {q1, q2 , q3 , q4}, 9, 
q1, {q4}): 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
12 
 𝐿 𝑀9 =
𝑤|𝑤 contém 11 ou 101 
como subcadeia
 
 𝐿 𝑀9 = 𝑢𝑣𝑤|𝑢 ∈ 0,1 ∗, 𝑤 ∈ 0,1 ∗, 𝑣 ∈ 11,101 
q1 q2 q3 q4 
0 
0 
0 1 
1 
 
1 
1 
 Exemplo: Computação de M9 sobre a entrada 
010110: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
13 
q1 início 
0-------------------- 
q1 
q2 
q3 
q3 q1 
q1 
q2 q3 q1 
q2 q3 q1 
q3 q1 
q1 q2 q3 q4 
0 
0 
0 1 
1 
 
1 
1 
q4 
1------------------ 
0------------------ 
1------------- 
1-------- 
0------ 
X 
X 
X 
q4 
q4 q4 
q4 
 Exemplo: Computação de M9 sobre a entrada 
010000: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
14 
q1 início 
0-------------------- 
q1 
q2 
q3 
q3 q1 
q1 
q1 
q1 
q1 q2 q3 q4 
0 
0 
0 1 
1 
 
1 
1 
1------------------ 
0------------------ 
0------------------ 
0------------------ 
0------------------ 
X 
q1 
X 
X 
 Operações de Concatenação e Fechamento sobre 
linguagens. 
 Concatenação 
 Seja Σ um alfabeto, e sejam 𝐿, 𝐿1e 𝐿2 subconjuntos 
de Σ∗ (linguagens sobre o alfabeto Σ): 
 A concatenação de 𝐿1 e 𝐿2, denotada por 𝐿1𝐿2, é o 
conjunto 𝑥𝑦|𝑥 ∈ 𝐿1 e 𝑦 ∈ 𝐿2 . 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
15 
 Fechamento (fecho de Kleene) 
 Define-se 𝐿0 = 𝜀 e 𝐿𝑛 = 𝐿𝐿𝑛−1 para 𝑛 ≥ 1. O fecho 
de Kleene (ou simplesmente fecho) de uma 
linguagem 𝐿, denotado por 𝐿∗, é o conjunto: 
 
𝐿∗ = 𝐿𝑖
∞
𝑖=0
 
 E o fecho positivo da linguagem 𝐿, denotado por 𝐿+, 
é o conjunto: 
𝐿+ = 𝐿𝑖
∞
𝑖=1
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
16 
 𝐿∗ denota as cadeias construídas pela 
concatenação de qualquer número de cadeias 
tomadas de 𝐿; 
 O conjunto 𝐿+ é semelhante, mas neste caso, as 
cadeias de zero palavras, cuja concatenação é 
definida como , são excluídas; 
 𝐿+ contém  se e somente se 𝐿 a contém; 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
17 
 Esta definição difere da definição do fechamento 
de alfabetos, onde 𝐴+ era definido como 
𝐴∗ − 𝜀 . 
 Note-se que no caso de linguagens podem 
ocorrer dois casos: 
 Se 𝜀 ∈ 𝐿, então 𝐿+ = 𝐿∗; 
 Se 𝜀 ∉ 𝐿, então 𝐿+ = 𝐿∗ − 𝜀 . 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
18 
 Exemplo 1: 
 Se 𝐿1 = 10,1 e 𝐿2 = 0011,11 . Então 
 𝐿1𝐿2 = 100011,1011,10011,111 
 Exemplo 2: 
 Se 𝐿1 = 10,11 e 𝐿2 = 0011,11 . Então 
 𝐿1𝐿2 = 100011,1011,110011,1111 
 Exemplo 3: 
 Se 𝐿1 = 10,11, . Então 
𝐿∗ =
𝜀, 10,11,1010,1011,1110,1111,101010,
101011,101110,101111,111010,111011,
111110,111111,⋯
 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
19 
Expressões Regulares 
 Uma expressão regular (ER) sobre um alfabeto Σ 
é indutivamente definida como se segue: 
a) ∅ é uma ER que denota a linguagem vazia; 
b) 𝜀 é uma ER que denota a linguagem contendo 
exclusivamente a cadeia vazia, ou seja 𝜺 ; 
c) qualquer símbolo 𝑥 ∈ Σ é uma ER e denota a 
linguagem contendo a cadeia unitária 𝑥, ou seja 𝒙 . 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
20 
Expressões Regulares 
 Uma Expressão Regular (ER) sobre um alfabeto 
Σ é indutivamente definida como se segue: 
d) Se 𝑟 e 𝑠 são ERs que denotam, respectivamente, as 
linguagens 𝑅 e 𝑆, então: 
i. 𝑟 + 𝑠 (ou 𝑟 | 𝑠 ) é uma ER e denota a linguagem 𝑅 ∪ 𝑆; 
ii. 𝑟𝑠 (ou 𝑟 ∙ 𝑠 ) é uma ER e denota a linguagem 
𝑢𝑣|𝑢 ∈ 𝑅, 𝑣 ∈ 𝑆 ; 
iii. 𝑟∗ é uma ER e denota a linguagem 𝑅∗; 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
21 
Expressões Regulares 
 Observações: 
 A concatenação sucessiva (*) tem precedência sobre a 
concatenação e a união 
 A concatenação tem precedência sobre a união 
 Uma linguagem gerada por um expressão regular r é 
representada por L(r) ou GERA(r) 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
22 
Exemplos: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
23 
Somente a cadeia aa. 
Expressão 
Regular 
Linguagem Representada𝑎𝑎 
𝑏𝑎∗ 
𝑎|𝑏 ∗ 
𝑎|𝑏 ∗𝑎𝑎 𝑎|𝑏 ∗ 
𝑎∗𝑏𝑎∗𝑏𝑎∗ 
𝑎 + 𝑏 ∗ 𝑎𝑎 + 𝑏𝑏 
𝑎 + 𝜀 𝑏 + 𝑏𝑎 ∗ 
0∗1∗2∗ Todas as cadeias de 0 seguidas de 1’s seguidas de 2’s 
Todas as cadeias que iniciam por b, seguido de zero ou 
mais a. 
Todas as cadeias contendo aa como subpalavra. 
Todas as cadeias contendo exatamente dois b 
Todas as cadeias que terminam com aa ou bb. 
Todas as cadeias que não possuem dois a consecutivos 
Todas as cadeias sobre o alfabeto 𝑎, 𝑏 
 Exercícios: Desenvolver expressões regulares 
que geram as seguintes linguagens sobre 
={a,b}: 
1. {w | w tem no máximo um par de a como 
subcadeia ou no máximo um par de b como 
subcadeia, nunca ambos na mesma cadeia}. 
2. {w | qualquer par de a antecede qualquer par de b, 
se existirem}. 
3. {w | w não possui aba como subpalavra}. 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
24 
 Equivalência entre AF’s e ER’s 
 Pode-se facilmente construir um AF com -
transições a partir de qualquer expressão regular. 
 O método deve ser aplicado para a base (casos (a), 
(b) e (c)) e indutivamente para cada tipo de 
construção das ER´s. 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
25 
a) Para expressão , construa o seguinte AF: 
 
 
b) Para ER , construa o seguinte AF: 
 
 
c) Para ER a (para algum a), construa o 
seguinte AF: 
 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
26 
q0 
qf 
qf q0 
a 
d) Para ER (A | B), construa a seguinte estrutura: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
27 
 
q0 
q0 
A 
B 
q0 
 
N 
e) Para ER AB, construa a seguinte estrutura: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
28 
q0 
q0 B A 
N 
q0 
 
 
 
f) Para ER A*, construa a seguinte estrutura: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
29 
q0 
A 
N 
 
 
 
 Exemplo: Converter a ER (ab | a)* em um AFN. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
30 
a 
a 
b 
b 
ab 
a b  
ab | a 
a b  
a 
 
 
 Exemplo: Converter a ER (ab | a)* em um AFN. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
31 
(ab | a)* 
a b  
a 
 
 
 
 Exemplo: Converter a ER (a | b)*aba em um AFN. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
32 
a 
a 
b 
b 
a | b 
a 
b 
 
 
 Exemplo: Converter a ER (a | b)*aba em um AFN. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
33 
(a | b)* 
 
a 
b 
 
 
 
 
aba 
a a  b  
 Exemplo: Finalmente.... AF para a ER (a | b)*aba. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
34 
(a | b)*aba 
a a  
a 
b 
 
 
 
 
 
b  
 
 
 
 Gramáticas regulares lineares: 
 Gramática linear à direita Se todas as produções são da 
forma A  wB ou A  w, com wT*; 
 Gramática linear à esquerda Se todas as produções são da 
forma A  Bw ou A  w; 
 Gramática linear unitária à direita linear à direita com |w| 
 1; 
 Gramática linear unitária à esquerda linear à esquerda 
com |w|  1; 
 Teorema: As quatro definições de gramáticas lineares 
são equivalentes. 
 Uma gramática regular é qualquer gramática linear 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
35 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 À Direita, GD 
S  aS | aB 
B  bB | bD 
D  cddd 
 À esquerda, GE 
S  Bcddd 
B  Bb | Ab 
A  Aa | a 
36 
 Exemplo: gramáticas lineares equivalentes: 
 GD e GE geram a mesma linguagem: a
+b+cddd 
 aa*bb*cddd 
 Transformação de GR linear à direita em AF 
 Para transformar uma GR G = (N, T, P, S) em um AF 
M = (E, , , e0, F), proceda como segue: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
37 
Algoritmo: Transformação de GR em AF 
Entrada: Uma Gramática Regular 𝐺 = 𝑁, 𝑇, 𝑃, 𝑆 
Saída: Um Autômato Finito 𝑀 = Σ,𝑄, 𝛿, 𝑒0, 𝐹 
Q ≔ 𝑁 ∪ 𝑒𝑓 , onde 𝑒𝑓 é um símbolo que não está em 𝑁; 
Σ ≔ 𝑇; 
𝑒0 ≔ 𝑆; 
se 𝑆 ⟶ 𝜀 ∈ 𝑃 então 
 𝐹 ≔ 𝑒𝑓, 𝑆 ; 
senão 
 𝐹 ≔ 𝑒𝑓 ; 
fim-se; 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
38 
Construa  de acordo com as seguintes regras: 
a) Para cada produção da forma 𝐵 ⟶ 𝑎 ∈ 𝑃, crie uma transição 
 
 𝛿 𝐵, 𝑎 = 𝑒𝑓; onde 𝑎 ∈ 𝑇 ∪ 𝜀 
 
b) Para cada produção da forma 𝐵 ⟶ 𝑎𝐶 ∈ 𝑃, crie uma transição 
 
 𝛿 𝐵, 𝑎 = 𝐶; 
 
c) Para todo 𝑎 ∈ 𝑇; deixe 𝛿 𝑒𝑓, 𝑎 indefinida (ou use o estado 
ERRO). 
 Transformação de GR linear à direita em AF 
 Para transformar uma GR G = (N, T, P, S) em um AF 
M = (E, , , e0, F), proceda como segue: 
 Transformação de AF em GR linear à direita 
 Para transformar um AF em uma gramática regular 
equivalente, proceda como segue: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
39 
Algoritmo: Transformação de AF em GR 
Entrada: Um Autômato Finito 𝑀 = Σ, 𝑄, 𝛿, 𝑒0, 𝐹 
Saída: Uma Gramática Regular 𝐺 = 𝑁, 𝑇, 𝑃, 𝑆 
N ≔ 𝑄; 
T ≔ Σ; 
S ≔ 𝑒0; 
Defina 𝑃 de acordo com as seguintes regras: 
 a) Se 𝛿 𝐵, 𝑎 = 𝐶 então adicione 𝐵 ⟶ 𝑎𝐶 em P; 
 b) Se 𝛿 𝐵, 𝑎 = 𝐶 e 𝐶 ∈ 𝐹, então adicione 𝐵 ⟶ 𝑎 em P; 
 c) Se 𝑒0 ∈ 𝐹, então adicione 𝑆 → 𝜀 em P. 
 Determinização de AFN 
 Por definição, todo AFD é um caso especial de AFND 
no qual a relação de transição é uma função; 
 A classe de linguagens reconhecidas por um AFND 
inclui as linguagens regulares (reconhecidas por 
AFD’s); 
 Pode-se provar que as linguagens regulares são as 
únicas linguagens reconhecidas por um AFN 
 Para tanto, basta mostrar que para qualquer AFN 
pode-se construir um AFD que reconhece a 
mesma linguagem. Um método de transformação é 
dado a seguir. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
40 
 Determinização de AFN 
 Ideia do algoritmo 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
41 
b 
c 
a 
a 
b 
c 
a 
c 
b 
a 
a 
 Determinização de AFN 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
42 
Algoritmo: Determinização de Autômato Finito 
Entrada: Um AFND MN = (E, A, t, e0, F) 
Saída: Um AFD MD = (E’, A, t’, e0, F’) 
 
1. Rotule a primeira linha da tabela de transições t’ para MD com um 
conjunto unitário contendo apenas o estado inicial e0 de MN. Aplique o 
passo (2) a este conjunto. 
 
2. Dado um conjunto de estados S, rotulando uma linha da tabela t’ para 
MD, para a qual as transições ainda não foram computadas, encontre os 
estados de MN que podem ser alcançados a partir dos estados contidos 
em S para cada símbolo de entrada; coloque estes estados na coluna 
correspondente ao símbolo de entrada na tabela para MD. 
 Determinização de AFN 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
43 
3. Para cada novo conjunto gerado pelas transições do passo (2), 
determine se ele já é usado como rótulo para alguma linha de MD. Se o 
conjunto ainda não foi usado, então crie uma nova linha com o conjunto 
como rótulo. Se o conjunto já foi usado, não é necessário fazer nada com 
ele. 
 
4. Se existe alguma linha em MD para a qual as transições não foram 
computadas, volte e aplique o passo (2) àquela linha. Se todas as 
transições já forma computadas, vá pra o passo (5). 
 
5. Para todas as linhas de MD rotuladas com conjuntos que contenham 
pelo menos um estado final de MN, marque estalinha como estado final 
de MD. Fim. 
 Exemplo - Construção de um AFD a partir do 
AFND M10: 
 Determinizar o AFND M10 = ({a,b}, {q0, q1, q2, qf}, t, 
q0, {qf}), dado a seguir. 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
44 
q0 q1 q2 
a 
a,b 
a 
qf 
a 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 Tabela t para o 
autômato M10: 
 Execução do algoritmo 
 
45 
 t a b 
 
 
 
 
 
* 
q0 
q1 
q2 
qf 
{q0, q1} 
{q2} 
{qf} 
- 
{q0} 
- 
- 
- 
t' a b 
q0 q01 q0 
q01 q01, q2 q0 
t' a b 
q0 q01 q0 
q01 q012 q0 
q012 q012, qf q0 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
 Tabela t’ completa:  Execução do algoritmo 
 
46 
t' a b 
q0 q01 q0 
q01 q012 q0 
q012 q012, qf q0 
t' a b 
q0 q01 q0 
q01 q012 q0 
q012 q012f q0 
q012f q012f q0 q1 q2 - 
q2 qf - 
qf - - 
 Tabela final: AFD equivalente ao AFN M10 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
47 
t' a b 
q0 q01 q0 
q01 q012 q0 
q012 q012f q0 
q1 q2 - 
q2 qf - 
qf - - 
q012f q012f q0 
 O AFD construído conforme o algoritmo, dado 
pela tabela anterior, é 
 M10D = ({a, b}, Q’, t’, q0, F’) 
 Onde: 
 Q’ = {q0, q1, q2, qf, q01, q012, q012f } 
 F’ = {qf, q012f}. 
 t’ = exibida a seguir (e na tabela anterior) 
 Ver diagrama a seguir 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
48 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
49 
q0 q01 q012f b 
a 
b 
q012 
a a 
b 
b 
a 
q1 qf q2 
a a 
 O AFD M10D equivalente ao AFND M10 
Exemplo: L={ w | w aceita cadeias terminadas em 01 } 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
50 
 Diagrama de transições: 
 Tabela de transições: 
q0 q2 
0 
1 
0 
q1 
1 
0 1 
q0 {q0, q1} {q0} 
q1 – {q2} 
q2 – – * 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
51 
q0 q2 
0 
1 
0 
q1 
1 
Exemplo: L={ w | w aceita cadeias terminadas em 01 } 
 Como o conjunto de estados é 𝑞0, 𝑞1, 𝑞2, , a 
construção de subconjuntos produz um AFD 
com 23 – 1 = 7 estados. 
 Estados possíveis do AFD obtidos do AFND: 
𝑞0, 𝑞1, 𝑞2, 𝑞01, 𝑞02, 𝑞12, 𝑞012 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
q0 q2 
0 
1 
0 
q1 
1 
* 
* 
* 
* 
Tabela do AFD 
0 1 
q0 {q0, q1} {q0} 
q1 – {q2} 
q2 – – * 
Exemplo: L={ w | w aceita cadeias terminadas em 01 } 
q01 q02 
0 1 
q0 
q1 
q2 
q01 
q02 
q12 
q012 
q01 q0 
– q2 
– – 
q01 q02 
q01 q0 
– q2 
 Construção da tabela do AFD equivalente 
52 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
53 
q0 q02 
1 
0 
q01 
1 
0 
1 
0 
Exemplo: L={ w | w aceita cadeias terminadas em 01 } 
q012 
0 1 
q2 
q1 
q12 
1 
1 
 AFD equivalente em forma de diagrama: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
54 
q0 q02 
1 
0 
q01 
1 
0 
1 
0 
Exemplo: L={ w | w aceita cadeias terminadas em 01 } 
 De todos os estados listados, só podemos 
acessar os estados q0, q01 e q02. Os demais 
estados são inacessíveis, logo podem ser 
removidos. Finalmente, obtém-se o seguinte 
AFD: 
 
 Exercício: Achar o AFD equivalente ao AFN 
abaixo: 
Linguagens Regulares – Gramáticas 
Regulares e Autômatos Finitos 
q1 q2 q3 
0 
0 1 
0 
1 
0 
q4 
q5 
1 
1 
0 1