Teoria da Computação 2008/09
Ficha de trabalho
Autómatos finitos deterministas
(palavra aceite, linguagem reconhecida, concepção)
1. Considere o autómato finito D=<Q,q0,I,δ, F> em que Q={q0,q1,q2,q3,q4},
F={q3}, I={a,b} e cujo diagrama de estados é o seguinte
Verifique se a sequência abbaabb é aceite por D. Caracterize a
linguagem LD.
2. Seja I={a,b} um alfabeto. Construa autómatos finitos deterministas que
aceitem as seguintes linguagens:
a) {baa, ab, abb}
b) Palavras que começam por a ou terminam em b;
c) Palavras que não terminam em ba;
d)
Palavras que contêm um número ímpar de sequências ab;
e)
Palavras cujo tamanho não é divisível por 6.
f)
Palavras que contêm vários triplos de a’s
g) Palavras que contêm dois b’s ou dois a’s;
h) Palavras que terminam com aa ou bb;
i) Palavras que não terminam com aa ou bb;
j) Palavras que não contêm bbb;
k) Palavras que não contêm ab;
l) Palavras cujo número de a’s é divisível por 3;
m) Palavras que contêm sequências de b’s de tamanho ímpar;
n) Palavras que contêm sequências de a’s de tamanho par e sequências
de b’s de tamanho ímpar.
o) Palavras, tais que entre dois a’s consecutivos, existe no máximo um b.
3. Considere a linguagem L sobre o alfabeto {0,1,x,+} cujas palavras se
escrevem da forma αxβ ou da forma α+β, onde α e β são sequências não
vazias de 0’s e de 1’s que começam por 1. Construa um autómato finito
que aceite L.
Departamento de Matemática / Universidade dos Açores
1
Teoria da Computação 2008/09
Ficha de trabalho
4. Considere a linguagem L sobre o alfabeto {x, ., @} cujas palavras se
escrevem da forma α@β, onde α∈{x}+ e β∈{x, .}+ é uma sequência que
começa e termina em x e não contém dois .’s consecutivos. Construa
um autómato finito que aceite L. Verifique se as seguintes sequencias
fazem parte da linguagem reconhecida: (i) [email protected]; (ii) xx@x; (iii)
[email protected]. .
5. Considere o alfabeto I={0,1,2}. Construa um autómato finito que aceite
cada uma das seguintes linguagens sobre I:
a. Palavras que terminam em 12;
b. Palavras que terminam em 2 e têm pelo menos dois 2’s e palavras que
terminam em 1 e não têm 2’s;
c. Palavras que terminam em 2 e têm um número par de dois 2’s e
palavras que terminam em 1 e não têm 2’s;
d. Palavras que têm exactamente dois 0’s entre dois 1’s consecutivos;
e. Palavras cuja soma de cada dois dígitos consecutivos é igual ou
inferior a 2;
f. Palavras cuja soma de cada dois dígitos consecutivos é ímpar;
g. Palavras que têm dois 0’s consecutivos e terminam em 2;
h. Palavras que não têm dois 0’s consecutivos e terminam em 2;
i. Palavras que têm um número ímpar de 1’s e terminam em 22;
j. Palavras que não começam com 1, terminam em 2 e têm um número
ímpar de 0’s.
6. Considere a seguinte descrição informal de um sistema:
Imagine que existem três interruptores 1, 2 e 3 que controlam a
iluminação da entrada de um edifício composta por duas lâmpadas: uma
situada a norte e a outra situada a sul. Os interruptores funcionam do
seguinte modo: o interruptor 1 acende ou apaga a lâmpada situada a
norte, consoante esta se encontre apagada ou acesa, respectivamente;
o interruptor 2 acende ou apaga cada uma das lâmpadas, consoante
estas se encontrem apagadas ou acesas, respectivamente; o interruptor
3 acende ou apaga a lâmpada situada a sul, consoante esta se encontre
apagada ou acesa, respectivamente.
Departamento de Matemática / Universidade dos Açores
2
Teoria da Computação 2008/09
Ficha de trabalho
Suponha que inicialmente as lâmpadas se encontram apagadas.
Construa um autómato finito que verifica se as duas lâmpadas se
encontram acesas, ou seja, deverá aceitar sequências em {1,2,3}* se e
só se após a execução, o efeito produzido das lâmpadas seja o de estas
se encontrarem acesas. Por exemplo, deverá aceitar a sequência 2132,
uma vez que esta corresponde a acender as lâmpadas, apagá-las em
seguida e acendê-las novamente. No entanto a sequência 23213 deverá
ser rejeitada, pois após a respectiva sequência de movimentos, a luz
situada a sul está apagada.
7. Considere a linguagem L formada por todas as sequências sobre o
alfabeto {0,1,2} cujo somatório seja divisível por 3. Construa um
autómato finito D que aceite L. Verifique se 1201 é aceite por D.
8. Considere o seguinte protocolo de transmissão de mensagens binárias
entre dois computadores.
• O início e o fim da transmissão é marcado pelos caracteres 00 e 11,
respectivamente.
• As mensagens são obrigatoriamente iniciadas por dois bits, indicativos
do seu comprimento.
• Entre duas mensagens há um separador constituído pelo padrão 101.
• Em todas as transmissões há, no mínimo, uma mensagem a transmitir.
Um exemplo de transmissão válida de mensagens é dado por:
init
size
msg
sep
size
msg
end
00
10
11
101
01
1
11
Construa um autómato finito que aceite o conjunto das mensagens
válidas.
9. Construa um autómato finito que aceite a linguagem formada pelos
números reais de vírgula fixa, mas sem 0’s supérfluos à esquerda ou à
direita da vírgula. Por exemplo a linguagem inclui 0,0 e 123,01 mas não
inclui 0,00 nem 010,0.
Departamento de Matemática / Universidade dos Açores
3