Lista de Exercícios
Disciplina: Linguagens Formais e Autômatos
Curso: Ciência da Computação – Unioeste
Prof. Rômulo
Data: 21/03/2008
Tópico: AFDs e gramáticas regulares.
1. Projete autômatos finitos determinísticos (AFD) que reconheça as linguagens
descritas a seguir:
a) ∑={a,b}, L = {w | w possui número ímpar de a’s e b’s em ∑*}
b) ∑={a,b}, L = {w | w possui número ímpar de a’s e número par de b’s em ∑*}
c) ∑={a,b}, L = {w | cada a em w é imediatamente precedido por um b em ∑*}
d) ∑={a,b}, L = {w | w não tem aa e nem bb como subpalavra em ∑*}
e) ∑={a,b,c}, L = {w | w tem ab ou bc como subpalavra em ∑*}
f) ∑={a,b,c}, L = {w | w não contém abc como subpalavra em ∑*}
g) ∑={a,b,c}, L = {w | todo b em w é seguido imediatamente por c em ∑*}
h) L = {anbmcp | n ≥ 1, m ≥ 1, p ≥ 1 }
i) L = {anbmcp | n ≥ 0, m ≥ 0, p ≥ 0 }
j) L = {anbmcp | n ≥ 0, m ≥ 1, p ≥ 0 }
k) L = {anbmcp | n ≥ 1, m ≥ 0, p ≥ 1 }
l) L = {anbmcp | n ≥ 1, m ≥ 0, p ≥ 1 }
m) L = {(ab)ncm | n ≥ 1, m ≥ 1 }
n) L = {(ab)ncm | n ≥ 0, m ≥ 0 }
o) L = {(ab)n(cd)m | n ≥ 0, m ≥ 0 }
2. Descreva as linguagens reconhecidas pelos AFDs a seguir:
a)
b
a
b
c
b)
0
1
c)
a
b
c
d)
3. Escreva uma gramática para cada uma das seguintes linguagens:
a) ∑={a,b,c}, L = { w | cada b é seguido por pelo menos um c em ∑*}
b) ∑={a,b}, L = { w | cada a é precedido ou seguido por um b em ∑*}
c) L = {anbmcp | n ≥ 1, m ≥ 1, p ≥ 1 }
d) L = {anbmcp | n ≥ 1, m ≥ 0, p ≥ 1 }
e) L = {anbm | n ≥ 1, m ≥ 0 } ∪ {bncm | n ≥ 1, m ≥ 0 }