Tema 07 - Autômatos Finitos Não Determinísticos - GABARITO DOS EXERCÍCIOS

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA DA COMPUTAÇÃO 
TEMA 7: Autômatos Finitos Não Determinísticos 
GABARITO DE ALGUNS EXERCÍCIOS 
 
1) Converter os AFN’s M2, M4, M5, M6 e M7 do TEXTO DE APOIO (Exercícios da Seção 7.4) nos seus AFD’s 
equivalentes. Verifique se os AFD’s reconhecem as linguagens correspondentes. 
a) L[M2] = L[ (avb)*aa ] 
q0
a,b
a
q2q1
a
 
 M2 
 
1º PASSO: grafo do AFN → tabela do AFN 
 
q0
a,b
a
q2q1
a
 
 
AFN a b 
> q0 {q0,q1} {q0} 
 q1 {q2} ∅ 
* q2 ∅ ∅ 
 
2º PASSO: tabela do AFN → tabela do AFD 
 
AFN a b 
> q0 {q0,q1} {q0} 
 q1 {q2} ∅ 
* q2 ∅ ∅ 
 
AFD a b 
> e0 = {q0} e1 = {q0,q1} e0 = {q0} 
 e1 = {q0,q1} e2 = {q0,q1,q2} e0 = {q0} 
* e2 = {q0,q1,q2} e2 = {q0,q1,q2} e0 = {q0} 
 
3º PASSO: tabela do AFD → grafo do AFD 
 
AFD a b 
> e0 e1 e0 
 e1 e2 e0 
* e2 e2 e0 
 
e0
b
a
b
e2e1
a
b a
 
 M2’ 
 
 
 
 
 
 
b) L[M4] = L[ (avb)*(aa v bb) ] 
q0
a,b
a
q2
q1 a
q3
b
b
 
 M4 
 
1º PASSO: grafo do AFN → tabela do AFN 
 
q0
a,b
a
q2
q1 a
q3
b
b
 
 
AFN a b 
> q0 {q0,q1} {q0,q3} 
 q1 {q2} ∅ 
* q2 ∅ ∅ 
 q3 ∅ {q2} 
 
2º PASSO: tabela do AFN → tabela do AFD 
 
AFN a b 
> q0 {q0,q1} {q0,q3} 
 q1 {q2} ∅ 
* q2 ∅ ∅ 
 q3 ∅ {q2} 
 
AFD a b 
> e0 = {q0} e1 = {q0,q1} e2 = {q0,q3} 
 e1 = {q0,q1} e3 = {q0,q1,q2} e2 = {q0,q3} 
 e2 = {q0,q3} e1 = {q0,q1} e4 = {q0,q2,q3} 
* e3 = {q0,q1,q2} e3 = {q0,q1,q2} e2 = {q0,q3} 
* e4 = {q0,q2,q3} e1 = {q0,q1} e4 = {q0,q2,q3} 
 
3º PASSO: tabela do AFD → grafo do AFD 
 
AFD a b 
> e0 e1 e2 
 e1 e3 e2 
 e2 e1 e4 
* e3 e3 e2 
* e4 e1 e4 
 
e0
a
b
e3e1
a
b a
e2
b
a
e4
a b
b
 
 M4’ 
 
 
 
 
 
 
 
 
 
 
 
c) L[M5] = L[ (avb)*aa(avb)* ] 
q0
a
q2
a,ba,b
q1
a
 
 M5 
 
1º PASSO: grafo do AFN → tabela do AFN 
 
q0
a
q2
a,ba,b
q1
a
 
 
AFN a b 
> q0 {q0,q1} {q0} 
 q1 {q2} ∅ 
* q2 {q2} {q2} 
 
2º PASSO: tabela do AFN → tabela do AFD 
 
AFN a b 
> q0 {q0,q1} {q0} 
 q1 {q2} ∅ 
* q2 {q2} {q2} 
 
AFD a b 
> e0 = {q0} e1 = {q0,q1} e0 = {q0} 
 e1 = {q0,q1} e2 = {q0,q1,q2} e0 = {q0} 
* e2 = {q0,q1,q2} e2 = {q0,q1,q2} e3 = {q0,q2} 
* e3 = {q0,q2} e2 = {q0,q1,q2} e3 = {q0,q2} 
 
3º PASSO: tabela do AFD → grafo do AFD 
 
AFD a b 
> e0 e1 e0 
 e1 e2 e0 
* e2 e2 e3 
* e3 e2 e3 
 
e0
b
a
b
e2e1
a
a
e3 b
b
a
 
 M5’ 
 
2) (d)