Baixe o app para aproveitar ainda mais
Prévia do material em texto
Área de Teoria DCC/UFMG Fundamentos de Teoria da Computação 2020/01 SOLUÇÃO DE LISTA DE EXERCÍCIOS Lista 1 - Parte 2/3 (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) 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 1 Solução do exerćıcio 1.12 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)) 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)) Solução do professor: Vamos construir um AFN para a ER (0 ∪ 1)∗000(0 ∪ 1)∗ usando o procedimento descrito no Lema 1.55. 5. (Sipser 1.20 - Itens (a), (e), (g)) 2 Solução do exerćıcio 1.19 - AFN para 0 Solução do exerćıcio 1.19 - AFN para 1 Solução do exerćıcio 1.19 - AFN para 0 ∪ 1 Solução do exerćıcio 1.19 - AFN para (0 ∪ 1)∗ Solução do exerćıcio 1.19 - AFN para 000 Solução do exerćıcio 1.19 - AFN para (0 ∪ 1)∗000(0 ∪ 1)∗ 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) Solução do professor: 3 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
Compartilhar