p1 2014.2

Prévia do material em texto

P1 — Linguagens Formais e Teoria da Computac¸a˜o, 2014.2
Prof. Christiano Braga
Instituto de Computac¸a˜o
Universidade Federal Fluminense
08/10/2014
Gabarito
1. (0.5 ponto) Neste curso, como sa˜o formalizadas linguagens e palavras numa linguagem?
Resposta:Conjuntos e elementos de um conjunto, respectivamente.
2. (1,5 ponto) Considere a palavra w = abcb sobre o alfabeto {a, b, c}. Responda:
(a) Quais sa˜o os prefixos de w?
(b) Quais sa˜o os sufixos de w?
(c) Quais sa˜o as subpalavras de w?
Resposta:
(a) ǫ, a, ab, abc, abcb
(b) ǫ, b, cb, bcb, abcb
(c) Qualquer prefixo ou sufixo.
3. (1 ponto)Considere o alfabetoΣ = {a, b}. Represente diagramaticamenteum autoˆmato que reconhec¸a:
(a) A linguagem vazia.
Resposta:
q0start
a, b
(b) Todas as palavras sobre Σ.
Resposta:
q0start
a, b
4. (2 pontos) Considere a linguagem L cujas palavras teˆm a, bb ou ccc como sufixo.
(a) Defina diagramaticamente um AFN ǫ que reconhec¸a L.
Resposta:
q0start q2
q1
q3
q4 q5 q6
qf
a,b,c ǫ
ǫ
ǫ
a
b b
c c
c
(b) Defina a expressa˜o regular que descreve L.
Resposta:
(a+ b+ c)∗(a+ bb+ ccc)
5. SejaM o AFD abaixo.
q0start q1 q2 qf
a a,b a,b
(a) (0,5 ponto) Qual e´ a linguagem aceita porM?
Resposta:
L = a(a+ b)(a+ b)
(b) (1,5 ponto) Seja L a linguagem aceita porM . Qual o AFD que aceita ∼ L, isto e´, o complemento
de L?
Resposta:
q0start q1 q2 qf
d
a
b
a,b a,b
a,b
a,b
6. (3 pontos) Minimize o autoˆmato abaixo.
Astart B C D
E F G H
0
1
0
1
0 1
0
1
0
1
0
1
0
1
0
1
Resposta:
2
{A,E}start {B,H} {C}
{F} {G}
0
1
0
1
0
1
0
1
0
1
3