Lista de Exercícios – Autômatos e Linguagens Formais – 2014
δ
1) Descreva graficamente a linguagem do AFD M = (K, Σ, δ, i, F), onde
q0
K={ q0, q1, q2, q3}, Σ = { a, b }, q0, F = { q2 }, e δ dada pela tabela ao lado: q1
q2
2) Assuma o autômato do exercício 1 e assinale as afirmações incorretas.
q3
a)
b)
c)
d)
a
q1
q2
q3
q0
b
q3
q0
q1
q2
A linguagem gerada L(M) contem cadeias tais que o número de a's é divisível por 2
A linguagem gerada L(M) não contem cadeias que terminam com b
A linguagem gerada L(M) não contem cadeias que iniciam com b
A linguagem gerada L(M) contem as cadeias { aba, abaaba abba}, entre outras.
3) Forneça AFDs que aceitam as seguintes linguagens sobre o alfabeto Σ = { 0, 1 }
a)
b)
c)
d)
e)
Conjunto de todas as cadeias que terminam em 00.
Conjunto de todas as cadeias com três zeros consecutivos, não necessariamente no final.
Conjunto de todas as cadeias que têm 011 como subcadeia
Conjunto de cadeias que começam ou terminam com 01.
Conjunto de cadeias tais que, o número de 0 s é divisível por 3 e o número de 1 s é divisível
por 2.
4) Dada a descrição gráfica do autômato A abaixo, descreva-o formalmente.
5) Assuma o autômato A do exercício 4 e assinale as afirmações incorretas.
a)
b)
c)
d)
A linguagem gerada L(A) contem as cadeias { bccababc, aaabaaac }
A linguagem gerada L(A) não contem cadeias com a subcadeia aaaa
A linguagem gerada L(A) não contem cadeias que iniciam com c
O autômato A é AFD.
6) Indique 5 cadeias que pertencem a Linguagem gerada por
cada autômato abaixo.