Folha 2.
Autómatos e respectivas linguagens
1. Identifique os AFD gerados a partir das seguintes expressões regulares :
a) s+
b) s? , que corresponde a s + ∅
c) (s + t) (s + t)
d) (s + t)*
2. Determine os AFD que aceitam as seguintes linguagens geradas sobre o alfabeto V = { 0, 1 }.
a) O conjunto das frases que terminam por 00.
b) O conjunto das frases que possuem uma subfrase formada por uma sequência de três zeros.
c) O conjunto das frases cujos blocos de 5 símbolos consecutivos possuem, pelo menos, um zero.
d) O conjunto das frases cujo penúltimo símbolo seja zero.
3. Considere o alfabeto V = { 0, 1 }.
a) Determine o AFD que aceite a linguagem formada pelo conjunto das frases que possuem a
subfrase 1 0 0 1 e terminam com 0.
b) Verifique se a frase 1 0 1 0 0 1 1 0 1 0 é aceite pelo AFD. Justifique através da apresentação da
sequência dos estados atingidos.
4. Considere o alfabeto V = { F, T }.
a) Determine o AFD que aceite a linguagem, sobre V, formada pelo conjunto das frases que se
iniciam com a subfrase T F F T , depois do sexto símbolo (inclusive) contenham a sub-frase
T T F e terminem com o símbolo F .
b) Verifique se a frase T F F T F T T F T F é aceite pelo AFD construído na alínea anterior
(apresente a sequência de estados atingidos por cada uma delas)
2
Autómatos e respectivas linguagens
5. Considere o alfabeto V = { 0, 1, 2 }.
a) Determine o AFD que aceite a linguagem formada pelo conjunto das frases que se iniciam
com a subfrase 0 1 2 , depois contenham a subfrase 2 1 0 2 1 e terminem com o símbolo 1 .
b) Verifique se a frase 0 1 2 0 2 1 0 2 1 0 2 1 é aceite pelo AFD construído na alínea anterior
(apresente a sequência de estados atingidos por cada uma delas)
6. Considere-se o alfabeto V = { digito, sinal, ponto }. O conjunto de números decimais é gerado
pela seguinte expressão regular :
(sinal + digito) (digito)* ponto digito (digito)*
Identifique o AFD que reconhece a linguagem definida por esta expressão regular.
7. Considere a seguinte expressão regular :
(a) (a + b)* b.
a) Identifique o AFD que permite reconhecer as sequências definidas pela expressão regular.
b) Verifique se o reconhecedor aceita as seguintes entradas como fazendo parte da linguagem
definida pela expressão regular :
(i) a
(ii) b
(iii) a b b
(iv) a b a
8. Considere a linguagem definida pela seguinte expressão regular :
a (b + c) + b (c + ε)
a) Indique quais as sequências pertencentes à linguagem indicada :
(i) a b c c c b c
(ii) a c c c b b c
(iii) a b b b b b c
(iv) a c b
b) Identifique um AFD que modele o reconhecedor da linguagem indicada. De seguida,
apresente o AFD equivalente.
9. Identifique a expressão regular que define os números reais de vírgula fixa, mas sem zeros
supérfluos à esquerda ou à direita da vírgula. Por exemplo, a linguagem inclui os números 0,0
e 123,01 mas não aceita 0.00 nem 010.0. Indique o AFD que reconheça essa linguagem.
10. Considere a seguinte expressão regular :
a (ab* + ba*) b*
Converta a expressão regular num AFD.
11. Considere a seguinte expressão regular :
(a + b)* + cd (a + b)*
Identifique o AFD que modela um reconhecedor da linguagem gerada pela expressão regular.
Folha prática 2
Autómatos e respectivas linguagens
3
12. Considere o seguinte protocolo de transmissão de mensagens binárias entre 2 computadores.
O início e o fim da transmissão é marcado pelos caracteres, respectivamente, 00 e 11. As
mensagens são obrigatoriamente iniciadas por 3 bits, indicativos do seu comprimento. Entre 2
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 010 11 101 001
1
11
a) Escreva a gramática descritora da transmissão de mensagens.
b) Converta a gramática numa expressão regular.
c) Converta a expressão regular num AFD.
d) Codifique o reconhecedor na linguagem de programação C.
13. Determine uma gramática regular geradora da linguagem aceite pelo autómato
A = (Q, T, M, q0, H)
onde
Q = { q0, q1, q2, q3 }
T = { a, b }
H = { q0 }
M
q0
q1
q2
q3
e M é tal que
a
q2
q3
q0
q1
b
q1
q0
q3
q2
14. Considere a seguinte tabela de transição de um autómato de pilha :
q
γ
s
q'
γ’
q1
q2
ε
ε
ε
1
q2
q2
ε
γ1
q2
γ1
1
q2
γ1 γ1
q2
γ2
1
q2
γ2 γ1
q2
ε
2
q2
γ2
q2
γ1
2
q2
γ1 γ2
q2
γ2
2
q2
γ2 γ2
q2
q2
ε
γ1
3
3
q3
q3
ε
γ1
q2
γ2
3
q3
γ2
q3
γ2
2
q3
ε
q3
γ1
1
q3
ε
Simule o comportamento do autómato de pilha apresentado perante as seguintes situações :
a) 1 2 1 1 3 1 1 2 1
b) 1 1 2 1 1 3 1 1 2 1
Folha prática 2
4
Autómatos e respectivas linguagens
c) 1 2 1 3 1 2 1 1
d) 1 2 1 1 3 1 1 2 1 1
e) 1 1 2 2 2 2 1 1
15. O autómato de pilha pode ser usado no cálculo de expressões representadas em notação pósfixada. Na notação pós-fixada são apresentados em primeiro lugar os dois operandos e depois
o operador : por exemplo, 2 3 * representa 2 × 3. Na notação pós-fixada não há parêntesis,
porque a posição dos operadores determina a ordem no cálculo das expressões : por exemplo,
2 3 4 * + representa a expressão 3 × 4 + 2 e 2 3 4 + representa ( 3 + 4 ) × 2.
Identifique um autómato de pilha que determina se a expressão de entrada é apresentada
segundo a notação pós-fixada.
Sugestão : Considere a entrada terminada sempre por um símbolo especial, $. No final do
reconhecimento, a pilha do autómato de pilha deve conter um número (o valor da expressão).
16. Identifique um autómato de pilha que reconheça uma linguagem de parêntesis, cujo alfabeto é
V = { (, ), [, ], <, > }.
17. Pretende determinar-se um autómato de pilha, A, tal que :
L(A) = { an bn : n = 1, 2, ... }
Folha prática 2