Gabarito P1 - Teoria da Computação - UERJ

•

UERJ

0

Camilla Menezes

29/08/2018

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você também pode ser Premium ajudando estudantes

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Teoria da Computação

1.495 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

q0 q1 
0 
q2 
1 
1 0 0,1 
Q.1) 
Q.2) (01)*.0.1.(01)* 
S  0A 
S  1S 
A  1B 
A  0A 
B  0B 
B  1B 
B  ε 
Q.3) 
G=<{S,A,B},{0,1},P,S> 
δ(S,0) = {A} 
δ(S,1) = {B} 
δ(A,1) = {C} 
δ(A,0) = {S} 
δ(B,0) = {C} 
δ(B,1) = {S} 
δ(C,0) = {B} 
δ(C,1) = {A} 
δ(C, ε) = {f} 
Q.4) 
M=<{S,A,B,C,f},{0,1}, δ, S, { f }> 
S  0A 
S  1B 
A  1C 
A  0S 
B  0C 
B  1S 
C  0B 
C  1A 
C  ε 
Gabarito A da P1 - Teoria da Computação – 2017-1 – 01/11/17 
M = <K, Σ, δ, i, F> 
δ(q0, 0 )={q0,q1} 
δ(q0, 1)={q0} 
δ(q1, 0)={q2} 
δ(q2, 0)={q2} 
δ(q2, 1)={q2} 
 
M’ = < K’, Σ, δ’, {q0}, F’> 
δ({q0}, 0)={q0, q1} 
δ({q0} ,1)={q0} 
δ({q0, q1},0)={q0, q1, q2} 
δ({q0, q1},1)={q0} 
δ({q0, q1, q2}, 0)={q0, q1, q2} 
δ({q0, q1, q2}, 1)={q0, q2} 
δ({q0, q2}, 0)={q0, q1, q2} 
δ({q0, q2}, 1)={q0, q2} 
Q.5) 
De AFND M = <K, Σ, δ, q0, F> 
p/ AFD M’ = <K’, Σ, δ’, {q0}, F’> 
F´= { {q0, q1, q2}, {q0, q2} }