lista0-sol

Prévia do material em texto

Introdução a Teoria da Computação
Primeira Lista de Exerćıcios - Soluções
Profa. Carmem Hara
Exerćıcio 1:
Considere o alfabeto Σ = {a, b} e a palavra w = abb.
a. qual o valor de |w| ?
Resp: 3
b. verdadeiro ou falso: se w pertence a Σ∗, então w.w também pertence a Σ∗.
Resp: verdadeiro
c. enumere todas as subpalavras, prefixos e sufixos de w.
Resp: subpalavras: ǫ, a, b, ab, bb, abb
prefixos: ǫ, a, ab, abb
sufixos: ǫ, b, bb, abb
d. enumere todas as palavras em Σ∗ com tamanho igual a 3.
Resp: aaa, aab, aba, baa, abb, bab, bba, bbb
e. qual o tamanho do conjunto Σ∗ ?
Resp: infinito
Exerćıcio 2:
Considere as seguintes linguagens:
L1 = {w ∈ {0, 1}
∗ |w contém número ı́mpar de 0’s}
L2 = {w ∈ {0, 1}∗ |w contém pelo menos dois 0’s }
2.1 Enumere todas as palavras pertencentes a L1 e L2 de tamanho 3.
L1: 011, 101, 110, 000
L2: 001, 010, 100, 000
2.2 Diga qual a linguagem resultante das seguintes operações:
a. L1 ∪ L2 = {w ∈ {0, 1}∗ |w contém pelo menos um 0}
b. L1 − L2 = {w ∈ {0, 1}∗ |w contém um 0} = {011, 101, 110}
c. L1 ∩ L2 = {w ∈ {0, 1}∗ |w contém um número ı́mpar maior que 3 de 0’s}
d. L1.L2 = {w ∈ {0, 1}∗ |w contém pelo menos três 0’s }
e. L2.L1 = {w ∈ {0, 1}∗ |w contém pelo menos três 0’s }
f. L1.L1 = {w ∈ {0, 1}∗ |w contém um número par maior que 2 de 0’s}
g. L2.L2 = {w ∈ {0, 1}
∗ |w contém pelo menos quatro 0’s }
h. L∗1 = {w ∈ {0, 1}
∗ |w = ǫ ou w contém pelo menos um 0}
i. L∗2 = {ǫ} ∪ L2 = {w ∈ {0, 1}
∗ | w = ǫ ou w contém pelo menos dois zeros}
Exerćıcio 3:
Reescreva as expressões regulares abaixo com expressões mais simples que denotam a mesma linguagem.
a. ∅∗ + a∗ + b∗ + (a + b)∗
Resp: (a + b)∗
b. ((a∗b∗)∗(b∗a∗)∗)∗
Resp: (a + b)∗
c. (a∗b)∗ + (b∗a)∗
Resp: (a + b)∗
Exerćıcio 4:
Explique informalmente (em português) a linguagem denotada pela expressão regular (((a∗a)b) + b).
Resp: palavras com zero ou mais a’s seguido de um b.
Exerćıcio 5:
Escreva uma expressão regular que defina as linguagens abaixo.
a. {w ∈ {a, b}∗| todo a é imediatamente precedido e imediatamente seguido de um b}
Resp: (b(ab)∗)∗ ou ǫ + b(b + ab)∗
1
b. {w ∈ {a, b}∗| w tem abab como substring}
Resp: (a + b)∗abab(a + b)∗
c. {w ∈ {a, b}∗| w não tem aba com substring}
Resp: b∗(a + bbb∗)∗b∗
d. {w ∈ {a, b}∗| w contem exatamente uma ocorrência do string aaa}
Resp: (b∗(ǫ + a + aa)bb∗)∗aaa(bb∗(ǫ + a + aa)b∗)∗
e. {w ∈ {a, b}∗| |w| > 3 }
Resp: (a + b)(a + b)(a + b)(a + b)+
Exerćıcio 6:
Construa um autômato que aceita cada uma das linguagens abaixo.
a. {w ∈ {a, b}∗| todo a é imediatamente precedido e imediatamente seguido de um b}
b. {w ∈ {a, b}∗| w tem abab como substring}
c. {w ∈ {a, b}∗| w não tem aba com substring}
d. {w ∈ {a, b}∗| w contem exatamente uma ocorrência do string aaa}
b a
b
b
q0 q1 q2
(a)
a b a b
a,b a,b
q0 q1 q2 q3 q4
(b)
q0 q1 q2 q3 q0 q1 q2
b
a
a
b
b
a
a,b b
a
b
b
a a
(c) (d)
b
a a a
b
b
a,b
q4 q5 q6 q7q3
b
a
Exerćıcio 7:
Construa o AFN que aceita a linguagem regular ((ab)∗ + (bc)∗)ab.
a b
b c
a b
Ε
Ε
Ε
Ε Ε
Ε
Ε
Ε
Ε
Ε Ε
Ε
Ε
Ε
Ε
Ε
Exerćıcio 8:
1. Mostre a evolução das configurações instantâneas a partir do estado inicial para o reconhecimento da palavra
bbaa.
[q0, bbaa] ⊢ [qo, baa] ⊢ [q2, aa] ⊢ [q3, a] ⊢ [q4, a] ⊢ [q3, ǫ] ⊢ [q4, ǫ]
2. Construa um AFD equivalente ao AFN.
a,b
b a
a
E
A B C
a
b
b
a
b
a
A = {q0, q1}
B = {q0, q1, q2, q4}
C = {q0, q1, q3, q4}
Resp:
q3
q0 q1
Ε b
b
q2
q4
2