Lista 1 2 - Solução

Prévia do material em texto

Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da
Computação 2021/2
SOLUÇÃO DE LISTA DE EXERCÍCIOS
Lista 1 - Parte 2
(Linguagens Regulares: Expressões Regulares)
Leitura necessária:
• Introdução à Teoria da Computação, 2a Edição (Michael Sipser):
– Caṕıtulo 1.3: Expressões Regulares
Revisão.
1. Responda formalmente às seguintes perguntas:
(a) O que é uma expressão regular? Dê sua sintaxe.
Solução do professor: R é uma expressão regular (ER) sobre um alfabeto Σ se R for:
1. a, para algum a no alfabeto Σ (representando a linguagem {a}),
2. � (representando a linguagem {�}),
3. ∅ (representando a linguagem vazia),
4. (R1 ∪R2), onde R1 e R2 são expressões regulares,
5. (R1 ◦R2), onde R1 e R2 são expressões regulares,
6. (R∗1), onde R1 é uma expressão regular.
(b) Em que sentido dizemos que expressões regulares são equivalentes a linguagens regulares?
Solução do professor: Linguagens regulares e expressões regulares são equivalentes no sentido
de que toda linguagem regular é exprimı́vel através de uma expressão regular, e toda expressão
regular denota uma linguagem regular.
Exerćıcios.
2. (Sipser 1.12) Seja
D = {w | w contém um número par de a’s e um número ı́mpar de b’s e não contém a subcadeia ab}.
Dê um AFD de 5 estados que reconheça D e uma expressão regular que gere D. (Sugestão: Descreva
D de maneira mais simples.)
1
Solução do professor: Note que a linguagem
D = {w | w contém um número par de a’s e um número ı́mpar de b’s e não contém a subcadeia ab}
pode ser reescrita como
D = {w |w contém um número par de a’s e um número ı́mpar de b’s,
e nenhum b ocorre depois de algum a}.
Isto quer dizer que a linguagem D está contida na linguagem b∗a∗ em que nenhum b ocorre após algum
a. Agora apenas precisamos restringir a linguagem b∗a∗ de forma a ter um número ı́mpar de b’s e
um número par de a’s. Isto pode ser feito concatenando b(bb)∗ (prefixos com um número ı́mpar de
b’s) com (aa)∗ (sufixos com um número par de a’s), o que resulta na seguinte expressão regular para
a linguagem D:
b(bb)∗(aa)∗.
Um AFD de 5 estados para a linguagem está representado na Figura a seguir.
3. (Sipser 1.18 - Todos os itens, menos o item (h)) Dê expressões regulares que gerem as linguagens do
exerćıcio 1.6. Em todos os itens o alfabeto é {0, 1}.
(a) {w | w começa com 1 e termina com 0}.
(b) {w | w contém pelo menos três 1’s}.
(c) {w | w contém a subcadeia 0101, i.e., w = x0101y para algum x e algum y}.
(d) {w | w tem comprimento pelo menos 3 e seu terceiro śımbolo é um 0}.
(e) {w | w começa com 0 e tem tamanho par, ou começa com 1 e tem tamanho ı́mpar}.
(f) {w | w não contém a subcadeia 110}.
(g) {w | o comprimento de w é no máximo 5}.
(i) {w | toda posição ı́mpar de w é um 1}.
(j) {w | w contém pelo menos dois 0’s e no máximo um 1}.
(k) {�, 0}.
(l) {w | w contém um número par de 0’s, ou contém exatamente dois 1’s}.
(m) O conjunto vazio.
(n) Todas as cadeias exceto a cadeia vazia.
2
Solução do professor:
(a) 1(0 ∪ 1)∗0
(b) 0∗10∗10∗1(0 ∪ 1)∗ ou (0 ∪ 1)∗1(0 ∪ 1)∗1(0 ∪ 1)∗1(0 ∪ 1)∗
(c) (0 ∪ 1)∗0101(0 ∪ 1)∗
(d) (0 ∪ 1)(0 ∪ 1)0(0 ∪ 1)∗
(e) 0((0 ∪ 1)(0 ∪ 1))∗ ∪ 1(0 ∪ 1)((0 ∪ 1)(0 ∪ 1))∗
(f) (0 ∪ 10)∗(� ∪ 1 ∪ 111∗) = (0 ∪ 10)∗1∗ (Dica: construa um AFD para a linguagem e o converta
em uma ER.)
(g) � ∪ (0 ∪ 1) ∪ (0 ∪ 1)2 ∪ (0 ∪ 1)3 ∪ (0 ∪ 1)4 ∪ (0 ∪ 1)5
(i) (1(0 ∪ 1))∗
(j) (1 ∪ �)0+0+ ∪ 0+(1 ∪ �)0+ ∪ 0+0+(1 ∪ �)
(k) � ∪ 0
(l) 1∗(01∗01∗)∗ ∪ 0∗10∗10∗
(m) ∅
(n) (0 ∪ 1)+
4. (Sipser 1.19 - Item (a)) Use o procedimento descrito no Lema 1.55 para converter as seguintes ex-
pressões regulares em AFNs.
(a) (0 ∪ 1)∗000(0 ∪ 1)∗
Solução do professor:
(a) Constrúımos um AFN para a ER (0 ∪ 1)∗000(0 ∪ 1)∗ usando o procedimento descrito no Lema
1.55 através do passo-a-passo abaixo.
3
5. (Sipser 1.20 - Itens (a), (e), (g)) Para cada uma das linguagens abaixo, dê duas cadeias que são
membros e duas cadeias que não são membros da linguagem – um total de quatro cadeias por item.
Assuma o alfabeto Σ = {a, b} em todos os itens.
(a) a∗b∗.
(e) Σ∗aΣ∗bΣ∗aΣ∗.
(g) (� ∪ a)b.
Solução do professor:
(a) L = a∗b∗. � ∈ L, a ∈ L, ba /∈ L, aba /∈ L.
(e) L = Σ∗aΣ∗bΣ∗aΣ∗. aba ∈ L, aaabaab ∈ L, � /∈ L, aab /∈ L.
(g) L = (� ∪ a)b. b ∈ L, ab ∈ L, � /∈ L, a /∈ L.
6. (Sipser 1.21) Use o procedimento descrito no Lema 1.60 para converter os seguintes autômatos finitos
em expressões regulares.
Solução do professor:
(a) Eliminando os estados na ordem 1, 2, obtenho a ER: (a∗b)(a ∪ ba∗b)∗
(b) Eliminando os estados na ordem 1, 3, 2, obtenho a ER: �∪ (a∪ b)(a∪ b(b∪ a(a∪ b)))∗(b(�∪ a)),
que pode ser reescrita de forma mais simples como � ∪ (a ∪ b)(a ∪ bb ∪ baa ∪ bab)∗(b ∪ ba).
4