Teoria de Linguagens - Exercícios Resolvidos

Prévia do material em texto

Departamento de Ciência da Computação ICEx/UFMG
Teoria de Linguagens 2o semestre de 2018
Professor: Newton José Vieira
Primeira Prova 18/9/2018 Valor: 24 pontos
1. Descreva, em português, as seguintes linguagens sobre o alfabeto {0, 1}:
a) {0, 1}∗{1}{0, 1};
b) {0}{0, 1}∗ ∪ {0, 1}∗{1};
c) {01, 1}∗;
d) {0}∗{1}({0} ∪ {1}{0}∗{1})∗.
Solução:
a) Conjunto das palavras cujo penúltimo śımbolo é 1.
b) Conjunto das palavras que começam com 0 ou terminam com 1.
c) Conjunto das palavras em que todo 0 (caso haja algum) é seguido de 1.
d) Conjunto das palavras com um número ı́mpar de 1s.
2. Construa gramáticas para as seguintes linguagens:
a) {0}{11}∗{0};
b) {w ∈ {a, b}∗ | o número de as em w é par};
c) {anbk |n > k};
d) {xxR |x ∈ {a, b}∗}.
Solução:
a) P → 0X0
X → 11X |λ
b) P → aI | bP |λ
I → aP | bI
c) X → aX | aXb | a
d) X → aXa | bXb |λ
3. Construa AFDs que reconheçam:
a) {0, 1}∗ − {0, 01, 10};
b) {w ∈ {0, 1}∗ |w tem número par de 0s e um único 1}.
Solução:
a)
0
1
1
0
0
0,1
1
0,1
b)
0
1
0
1
00
4. Sejam:
• L1 = {0, 1}
∗{1}{0, 1}∗;
• L2 = {w ∈ {0, 1}
∗ |w contém número par de 0s}.
Construa AFDs que reconheçam:
a) L1.
b) L2.
c) L1 − L2. Para isto, faça o produto dos autômatos que reconhecem L1 e L2.
Solução:
(a)
A B
1
0 0,1
(b)
1 2
1
0
1
0
(c)
A1
B1
A2
B2
0
1
0
1
1
0
1
0
5. Seja o AFN com o diagrama de estados:
1
2
3
4 5
0
1
0,1
1
0,1
0
0
Obtenha um AFD equivalente utilizando o método de construção de subconjuntos.
Solução:
15
24
3
2
34
0
1
1
0
1
0
0
1
0
1
6. Seja o AFNλ:
1
2
3
0
1
1
1
0
4 5
0
1
0
λ
Obtenha um AFN equivalente usando a técnica para eliminação de transições λ.
Solução:
1
2
3
0
1
1
1
0
4 5
0
1
01
1
1
Para e = 1, 2, 3: δ′(e, 1) = fλ(δ(e, 1)) = fλ({3}) = {3, 4}.