Exercícios resolvidos sobre AFN do 1º/2014

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 2
1. Construa o diagrama de estados de um autoˆmato finito (determin´ıstico ou na˜o) que reco-
nhec¸a a linguagem L = {w| cada ocorreˆncia da subcadeia aa (se existe) em w e´ imedia-
tamente seguida pela subcadeia bb}, sobre o alfabeto {a, b}. Fornec¸a tambe´m a definic¸a˜o
formal do autoˆmato como uma 5-upla.
Resposta:
q0 q1 q2 q3
b
a
b
a b
b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1} e δ : Q×Σε →
P(Q) e´ definida pela tabela
a b ε
q0 {q1} {q0} ∅
q1 {q2} {q0} ∅
q2 ∅ {q3} ∅
q3 ∅ {q0} ∅
2. Construa o diagrama de estados de um autoˆmato finito (determin´ıstico ou na˜o) que reco-
nhec¸a a linguagem L = {w| a quantidade de as em w e´ mu´ltiplo de 3 ou w na˜o conte´m a
subcadeia bb}, sobre o alfabeto {a, b}. Fornec¸a tambe´m a definic¸a˜o formal do autoˆmato
como uma 5-upla.
Resposta:
q0
q1
q2
q3
ε
b
a
b
a
b
a
q4 q5 q6
ε
a
b
a
b a,b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5, q6}, F = {q1, q4, q5} e
δ : Q× Σε → P(Q) e´ definida pela tabela
a b ε
q0 ∅ ∅ {q1, q4}
q1 {q2} {q1} ∅
q2 {q3} {q2} ∅
q3 {q1} {q3} ∅
q4 {q4} {q5} ∅
q5 {q4} {q6} ∅
q6 {q6} {q6} ∅
3. Construa o diagrama de estados de um autoˆmato finito (determin´ıstico ou na˜o) que reco-
nhec¸a a linguagem L = {w| o penu´ltimo s´ımbolo de w na˜o e´ a}, sobre o alfabeto {a, b}.
Atenc¸a˜o: note que as cadeias ε, a e b pertencem a L. Fornec¸a tambe´m a definic¸a˜o formal
do autoˆmato como uma 5-upla.
Resposta:
q0 q1 q2
q3
b
a a
a
b
b
b
a
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3}, F = {q0, q1} e δ : Q×Σ →
Q e´ definida pela tabela
a b
q0 q1 q0
q1 q2 q3
q2 q2 q3
q3 q0 q0
4. Construa o diagrama de estados de um autoˆmato finito (determin´ıstico ou na˜o) que reco-
nhec¸a a linguagem L = {w| a quantidade de as em w e´ par ou w na˜o conte´m a subcadeia
bab}, sobre o alfabeto {a, b}. Fornec¸a tambe´m a definic¸a˜o formal do autoˆmato como uma
5-upla.
Resposta:
q0
q1 q2ε
b
a
a
b
q3 q4 q5 q6
ε
a
b
b
a
a
b a,b
Definic¸a˜o formal: M = (Q,Σ, δ, q0, F ), onde Q = {q0, q1, q2, q3, q4, q5, q6}, F = {q1, q3, q4, q5}
e δ : Q× Σε → P(Q) e´ definida pela tabela
a b ε
q0 ∅ ∅ {q1, q3}
q1 {q2} {q1} ∅
q2 {q1} {q2} ∅
q3 {q3} {q4} ∅
q4 {q5} {q4} ∅
q5 {q3} {q6} ∅
q6 {q6} {q6} ∅