Exercícios resolvidos sobre AFD e AFN

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 2
Construa um AFD que reconhec¸a a linguagem
L = {w| o comprimento de w e´ pelos menos 3 e o terceiro s´ımbolo e´ um 0}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta:
q0 q1 q2 q3
q4
0,1 0,1 0 0,1
1
0,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4}, F = {q3} e δ : Q× Σ → Q
e´ definida pela tabela
0 1
q0 q1 q1
q1 q2 q2
q2 q3 q4
q3 q3 q3
q4 q4 q4
Construa um AFD que reconhec¸a a linguagem
L = {w| w conte´m um 0 em cada posic¸a˜o ı´mpar}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta:
q0 q1
q2
0
0,1
1
0,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2}, F = {q1} e δ : Q × Σ → Q e´
definida pela tabela
0 1
q0 q1 q2
q1 q0 q0
q2 q2 q2
Construa um AFN que reconhec¸a a linguagem
{w| o comprimento de w e´ divis´ıvel por 3 ou w comec¸a com 0}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta:
q0
q1 q2
q3 q4 q5
ε
0
0,1
ε
0, 1 0, 1
0, 1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5}, F = {q2, q3} e δ :
Q× Σε → P(Q) e´ definida pela tabela
0 1 ε
q0 ∅ ∅ {q1, q3}
q1 {q2} ∅ ∅
q2 {q2} {q2} ∅
q3 {q4} {q4} ∅
q4 {q5} {q5} ∅
q5 {q3} {q3} ∅
Construa um AFN que reconhec¸a o complemento da linguagem
{w| w tem comprimento 2 e termina com 0}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta:
q0 q1 q2 q3
0, 1 0 0, 1
0, 1
1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1, q3} e δ : Q×Σε →
P(Q) e´ definida pela tabela
0 1 ε
q0 {q1} {q1} ∅
q1 {q2} {q3} ∅
q2 {q3} {q3} ∅
q3 {q3} {q3} ∅
Construa um AFN que reconhec¸a a linguagem
{w| o comprimento de w e´ pelo menos 2 ou w na˜o termina com 10}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta: Se consideram a linguagem dada como a unia˜o de L1 =
{w| o comprimento de w e´ pelo menos 2} com o complemento de L2 =
{w| w termina com 10}, obtemos
q0
q1 q2 q3
q4 q5 q6
ε
0,1 0,1
0,1
ε
1
0
0
1
1
0
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5, q6}, F = {q3, q4, q5} e
δ : Q× Σε → P(Q) e´ definida pela tabela
0 1 ε
q0 ∅ ∅ {q1, q4}
q1 {q2} {q2} ∅
q2 {q3} {q3} ∅
q3 {q3} {q3} ∅
q4 {q4} {q5} ∅
q5 {q6} {q5} ∅
q6 {q4} {q5} ∅
Por outro lado, notem que, se w /∈ L1, enta˜o w ∈ L2. Assim, qualquer cadeia sobre {0, 1}
pertence a` linguagem dada, e um auto´mato que a reconhece e´, simplesmente,
q0 0,1
cuja definic¸a˜o formal e´ M = ({q0}, {0, 1}, δ, q0, {q0}), com δ(q0, 0) = δ(q0, 1) = {q0} e δ(q0, ε) =
∅.
Construa um AFD que reconhec¸a a linguagem
{w| o comprimento de w na˜o e´ divis´ıvel por 3}.
Desenhe o diagrama de estados e fornec¸a tambe´m a definica˜o formal. Considere o alfabeto {0, 1}.
Resposta:
q0 q1
q2
0,1
0,10,1
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2}, F = {q1, q2} e δ : Q × Σ → Q e´
definida pela tabela
0 1
q0 q1 q1
q1 q2 q2
q2 q0 q0