Baixe o app para aproveitar ainda mais
Prévia do material em texto
Área Conhecimento em Algoritmos e Teoria DCC/UFMG Fundamentos de Teoria da Computação 2021/2 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. (b) Em que sentido dizemos que expressões regulares são equivalentes a linguagens regulares? 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.) 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. 4. (Sipser 1.19 - Item (a)) Use o procedimento descrito no Lema 1.55 para converter as seguintes ex- pressões regulares em AFNs. 1 (a) (0 ∪ 1)∗000(0 ∪ 1)∗ 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. 6. (Sipser 1.21) Use o procedimento descrito no Lema 1.60 para converter os seguintes autômatos finitos em expressões regulares. 2
Compartilhar