Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Palavras, Linguagens e Expressões Regulares — Exercícios

Otimização Prematura
O xkcd obrigatório.

Indicações gerais para os exercícios de implementação

Quase todos os exercícios de implementação descrevem uma função ou estrutura de dados sujeita a algumas condições. É da sua responsabilidade testar os casos suficientes para assegurar o comportamento esperado.

A linguagem de programação que usar é indiferente, desde que não dê tiros nos pés com opções aberrantes tipo “C” ou “COBOL”. Ou “JavaScript”. Principalmente “JavaScript”.

Também não é fundamental a maneira como organiza o código, seja em classes ou de outra forma, desde que o organize logicamente.

Mais alguns princípios gerais importantes:

  • Os atributos das estruturas devem ter permissões tão restritas quanto possível. Se não for necessário alterar um atributo, não o permita. Se o atributo não tem de ser lido, esconda-o.
  • DRY, Don’t Repeat Yourself, Não se repita. Se está a escrever código repetido está a fazer um disparate. Grande. Pare imediatamente e pense como vai evitar as repetições repetições.
  • Premature optimization is the root of all evil, A otimização prematura é a raiz de todos os males. O seu código pode ser sempre melhorado: mais rápido, mais geral, mais específico, mais isto e aquilo. Se a melhoria não for necessária não perca tempo com ela.
  • Use as ferramentas e adquira os conhecimentos do Engenheiro Informático que vai ser:
    • Escolha e use ferramentas com boas comunidades e suporte. Torne-se fluente no seu ambiente de trabalho, na linha de comandos, no editor/ide, a usar repositórios, debuggers, testes, linters, profilers, etc.
    • Se ainda não o fez, instale um sistema operativo no seu computador. Infelizmente, em geral, os computadores quando vêm da loja trazem instalada uma coisa que mal serve para utilizadores amadores. Instale e use um sistema operativo baseado em unix, como o linux, o bsd ou o macos.
  • Este curso é de Engenharia Informática. Não permita que se confunda com uma qualquer “furmassão avançada de web-bonecos e insta-qualquer-coisa” daquelas que abundam nos motores de pesquisa — basicamente porque GIGO: Garbage In, Garbage Out.
    • Invista tempo e esforço a identificar, compreender e resolver as dificuldades. Procure as melhores referências, fale com colegas e com professores — nada com valor é rápido ou fácil.

Os exercícios assinalados com “✓” serão resolvidos nas aulas práticas; Os assinalados com “†” têm elevada dificuldade. Todos os restantes devem ser resolvidos pelos alunos.

Alfabetos, Palavras e Linguagens

Exercício 01

  1. Defina alfabetos para:
    1. Escrever os números naturais $0, 1, 2, \ldots$ em notação hexadecimal.
    2. Representar a configuração de um semáforo, no que diz respeito aos automóveis.
    3. Escrever as palavras da língua portuguesa.
    4. Escrever frases em português.
  2. Seja $\Sigma = \set{0, 1, 2}$ um alfabeto, $u = 012$ e $v = 22021$ palavras sobre $\Sigma$. Escreva por extenso as seguintes palavras:
    1. $uv$
    2. $vu$
    3. $v^R$
    4. $u^3$
    5. $012^3$
    6. $(012)^3$
    7. $v^0u$
    8. $(v^2)^R$

Exercício 02

Liste todas as sub-palavras, todos o prefixos e todos os sufixos das seguintes palavras sobre o alfabeto $\Sigma=\set{0, 1, 2, 3}$:

  1. $01023$
  2. $11111$
  3. $\nil$

Exercício 03

Seja $\Sigma = \set{a, b}$. Construa definições recursivas dos seguintes conjuntos:

  1. $C_1 = \set{\text{palavras sobre } \Sigma \text{ tais que o símbolo } a \text{ ocorre aos pares}}$. $C_1$ inclui, por exemplo, $bbaab$ e $aaaa$ mas não inclui $aaa$ nem $aabaaaba$.
  2. $C_2 = \set{p \in \cl{\Sigma} \st \len{p} \text{ é par }, p \text{ começa por } a \text{ e, em }p\text{, os } a \text{ e os } b \text{ ocorrem alternados}}$.
  3. $C_3 = \set{p \in \cl{\Sigma} \st p\ \text{é capicua}}$.
  4. ✓ $C_4 = \set{a^nb^n \in \cl{\Sigma} \st n > 0}$.
  5. $C_5 = \set{a^ib^j \in \cl{\Sigma} \st 0 \leq i < j}$.
  6. ✓ $C_6 = \set{p \in \cl{\Sigma} \st \len{p}_a = \len{p}_b}$. Sugestão: Use a concatenação no passo recursivo.

Exercício 04

Encontre a menor palavra sobre o alfabeto $\Sigma = \set{0}$ que não está em $\set{\nil, 0, 0^2, 0^5}^3$.

Exercício 05

  • † Demonstre as propriedades do fecho de linguagens.
  • † Demonstre as propriedades da concatenação de expressões regulares.

Exercício 06

Na ordem lexicográfica, quantas palavras estão entre $0$ e $1$? E na ordem mista?

Exercício 07

Desenhe os diagramas das seguintes linguagens:

  1. $\set{0^n \st n\ \text{é par}}$.
  2. $\set{p \in \cl{\set{0, 1}} \st \len{p} \leq 4}$.
  3. $\set{0^n1^n \st n \geq 0}$.
  4. $\set{0^n1^m \st n, m \geq 0}$.

Exercício 08

Descreva recursivamente o conjunto das palavras sobre o alfabeto $\set{a, b}$…

  1. com número par de símbolos.
  2. com número par de ocorrências de $a$.
  3. com número par de ocorrências de $a$ e número ímpar de ocorrências de $b$.
  4. com número ímpar de símbolos ou com menos de $n$ símbolos.
  5. com número ímpar de símbolos ou com, pelo menos, $n$ símbolos.
  6. com número ímpar de símbolos e com menos de $n$ símbolos.
  7. com número ímpar de símbolos e com, pelo menos, $n$ símbolos.
  8. de comprimento menor do que $n$ e com numero par de ocorrências de $b$.
  9. formadas por um certo número de $a$, seguido de um único $b$, seguido do mesmo número de $a$.

Exercício 09

  1. Calcule $\set{0, 1}\set{1, 2}$ e compare com $\set{1, 2}\set{0, 1}$. Enuncie o que observou como uma propriedade geral das operações de linguagens.
  2. É verdade que $\len{AB} = \len{A}\len{B}$?
  3. Sejam $A = \set{ (01)^n \st n\geq 0}$ e $B = \set{01, 010}$. Calcule $AB$ e $ABA$.
  4. Verifique que $\cl{\set{0, 10}}$ é a linguagem das palavras binárias que não têm $11$ como subpalavra e que terminam em $0$.
  5. † Confirme que $A^+ = \cl{A}$ se e só se $\nil \in A$.
  6. † Confirme que $\del{AB}^R = B^R A^R$ e que $\del{A \cup B}^R = A^R \cup B^R$.

Exercício 10

Mostre que, se $A, B$ forem linguagens então $\clpar{A \cup B} = \cl{A} \clpar{B\cl{A}}$.

Lembre-se que para provar que dois conjuntos $X, Y$ são iguais tem de provar as duas inclusões $X \subseteq Y$ e $Y \subseteq X$.

Exercício 11

Sejam $A = \set{\tt anti, pro, \nil}, B=\set{\tt pesso, soci}, C= \set{\tt al}$. O que são $ABC$ e $\cl{A}BC$?

Exercício 12

† Seja $A$ uma linguagem sobre $\set{0, 1}$ e $p \in \cl{\set{0, 1}}$. Encontre condições necessária e suficientes para que se verifique $\cl{A}\setminus\set{x} = A^+$.

Exercício 13

Verifique, com demonstrações ou contra-exemplos, quais das seguintes igualdades são válidas para todas as linguagens:

  1. $\clpar{A^R} = \del{\cl{A}}^R$.
  2. $\clpar{A^+} = \cl{A}$.
  3. $\clpar{A\cup A^R} = \cl{A} \cup \del{\cl{A}}^R$.
  4. $A^2 \cup B^2 = \del{A\cup B}^2$.
  5. $\cl{A} \cap \cl{B} = \clpar{A\cap B}$.

Exercício 14

Mostre que para $n \geq 1$:

  1. $\bigcup_{i=0}^n A^i = \del{\set{\nil} \cup A}^n$.
  2. $\del{\cl{A}}^n = \cl{A}$.
  3. Se $\nil \not\in A$ então $\del{A^+} = A^n \cl{A}$.

Exercício 15

Demonstre as seguintes igualdades:

  1. $A\clpar{BA} = \clpar{AB}A$.
  2. $\clpar{A \cup B} = \clpar{\cl{A}\cl{B}}$.
  3. $A\del{B\cup C} = AB \cup AC$.
  4. $\del{A \cup B}C =AC \cup BC$.
  5. $\cl{A}B\clpar{D\cl{A}B\cup C} = \clpar{A \cup B\cl{C}D}B\cl{C}$.

Expressões Regulares

Exercício 16

✓ Considere a expressão regular $\clpar{11 \cup 0}\clpar{00 \cup 1}$ e o respetivo diagrama.

  1. Encontre uma palavra incompatível com esta expressão regular.
  2. O que acontece se remover a aresta $\nil$ central do diagrama simplificado?

Exercício 17

  1. Desenhe e simplifique o diagrama de $\cl{a}b\clpar{c \cup d\cl{a}}$.
  2. Encontre a mais curta palavra não vazia das linguagens das seguintes expressões:
    1. $10\cup \del{0 \cup 11}\cl{0}1$.
    2. $\clpar{00 \cup 11 \cup \del{01 \cup 10}\clpar{00 \cup 11}\del{01 \cup 10}}$.
    3. $\clpar{\clpar{00 \cup 11} \cup \clpar{001 \cup 110}}$.
  3. Defina informalmente um algoritmo para encontrar a menor palavra numa linguagem regular definida por:
    1. Uma expressão regular.
    2. O diagrama de uma expressão regular.

Exercício 18

  1. Desenhe os diagramas das seguintes expressões regulares:

    1. $\del{00 \cup 10}\clpar{101}\cup 01$.
    2. $\clpar{\clpar{00 \cup 11} \cup \clpar{001 \cup 110}}$.
    3. $\clpar{a \cup b\cl{c}d}b\cl{c}$.

  2. Determine as expressões regulares definidas pelos seguintes diagramas:

    Fig. Ex 18.1   Fig. Ex 18.2   Fig. Ex 18.3

  3. Determine o menor diagrama que representa $\nil$.

  4. Encontre exemplos que mostram a necessidade de cada uma das condições do teorema da remoção das arestas $\nil$.

Exercício 19

Construa uma expressão regular para representar os números reais sem sinal, de acordo com as seguintes regras:

  • Um número real tem sempre uma vírgula decimal.
  • Um número real começa por 0 se e só se a sua parte inteira é 0.
  • Um número real termina em 0 se e só se a sua parte decimal é 0.

Exercício 20

Encontre expressões regulares para representar as seguintes linguagens:

  1. ✓ A linguagem das palavras sobre $\set{a,b,c}$ em que todos os $a$’s precedem todos os $b$’s que, por sua vez, precedem todos os $c$’s (donde que todos os $a$’s precedem todos os $c$’s), podendo não haver nem $a$’s, nem $b$’s, nem $c$’s.
  2. ✓ A linguagem da alínea anterior sem a palavra vazia.
  3. As palavras sobre $\set{a,b,c}$ de comprimento inferior a 3.
  4. As palavras sobre $\set{a,b,c}$ que começam por $a$, acabam em $cc$ e têm exatamente dois $b$’s.
  5. A linguagem das palavras sobre $\set{a,b}$ que têm $aa$ e $bb$ como subpalavras.
  6. As palavras sobre $\set{a,b}$ de que $bba$ não é subpalavra.
  7. ✓ A linguagem das palavras sobre $\set{a,b}$ que não têm prefixo $aaa$.
  8. ✓ A linguagem das palavras sobre $\set{a,b}$ que não têm $aaa$ como subpalavra.
  9. As palavras sobre $\set{a,b}$ em que $ab$ não ocorre.
  10. As palavras sobre $\set{a,b}$ em que $ab$ ocorre.
  11. As palavras sobre $\set{a,b}$ em que $ab$ ocorre só uma vez.

Exercício 21

Descreva informalmente as linguagens representadas pelas seguintes expressões regulares:

  1. $(a \cup b \cup c)(a \cup b \cup c)\AST $.
  2. $(a \cup b)((a \cup b)(b \cup a))\AST $.
  3. $5 \cup (1 \cup 2 \cup \cdots \cup 9)(0 \cup 1 \cup \cdots \cup 9)\AST (0 \cup 5)$.
  4. $c\AST (a \cup b)(a \cup b \cup c)\AST $.
  5. $(a(b \cup c)\AST a \cup b \cup c)\AST $.

Exercício 22

Simplifique as seguintes expressões regulares:

  1. ✓ $\emptyset\AST \cup a\AST \cup b\AST (a \cup b)\AST $
  2. $aa\AST b \cup b$
  3. ✓ $b\AST (a \cup (b\AST a\AST )\AST )ab\AST (ab\AST )\AST b$
  4. † $(a\AST b)\AST \cup (b\AST a)\AST $

Exercício 23

Encontre uma expressão regular para as seguintes linguagens binárias:

  1. Que representam as potências de $4$.
  2. Com, pelo menos, uma ocorrência de $001$.
  3. † Que não têm $001$ como subpalavra.
  4. Com, quanto muito, uma ocorrência de $00$ e, quanto muito, uma ocorrência de $11$.
  5. Em que nenhum prefixo tem mais dois $0$s que $1$s nem mais dois $1$s que $0$s.

Exercício 24

Verifique as igualdades $$ \begin{aligned} \cl{0}\clpar{0 \cup 1} &= \clpar{0 \cup \cl{10}} \cr \del{10}^+\del{ \cl{0} \cl{1} \cup \cl{ 0}} &= \clpar{10} \cl{10^+ 1} \end{aligned} $$

Exercício 25

  1. Descreva em linguagem natural as linguagens das seguintes expressões regulares:

    1. $\clpar{ \cl{0} \cl{1}} 0$.
    2. $\clpar{ \cl{0 1}} 0$.
    3. $\clpar{00 \cup 11 \cup \del{01 \cup 10}\clpar{00 \cup 11} \del{01 \cup 10}}$.
    4. $\cl{0} \cup \del{\cl{0} 1 \cup \cl{0} 11}\clpar{0^+ 1 \cup 0^+ 11} \cl{0}$.

  2. Simplifique as seguintes expressões regulares:

    1. $\del{00}\AST 0 \cup \del{00\AST}$.
    2. $\del{0\cup 1}\del{\nil \cup 00}^+ \cup \del{0 \cup 1}$.
    3. $\del{0\cup \nil}0\AST 1$.

  3. Mostre que $\del{0^2 \cup 0^3}\AST = \del{0^2 0\AST}\AST$.

Exercício 26

Defina expressões regulares para as linguagens binárias das palavras que:

  1. O quinto símbolo a contar da direita é $0$.
  2. Têm $000$ ou $111$ como subpalavra.
  3. Não têm $000$ nem $111$ como subpalavra.
  4. Não têm $010$ como subpalavra.
  5. Têm um número ímpar de $0$s.
  6. Têm um número par de ocorrências de $011$.

Exercício 27

Defina uma ER para as datas de acordo com a Norma ISO 8601. Considere só o caso YYYY-MM-DD:

  1. Permita que sejam representadas datas incorretas, como 2014-34-96.
  2. Restrinja os valores para os meses e para os dias, mas permita ainda dias inconsistentes com o mês. Por exemplo, 2014-02-31.
  3. Restrinja os valores para os dias de forma a serem consistentes com o mês, mas ignore o anos bissextos (isto é, assuma que fevereiro tem sempre 28 dias). Por exemplo 2004-02-29 não é válida.
  4. Trate dos anos bissextos.

Um ano bissexto é um ano múltiplo de 4 (por exemplo, 1948 é bissexto), exceto se também é múltiplo de 100 (por exemplo, 1900 não é bissexto) mas os múltiplos de 400 são sempre bissextos (por exemplo, 1600 é bissexto).

Implementação

Programa 00

Escreva uma função, listWords(fileName) que lê o ficheiro de texto fileName e produz a lista de palavras que ocorrem (sequencialmente) nesse ficheiro. Descarte os símbolos de pontuação e converta as letras para minúsculas. Sugestão: consulte a documentação de str e de string do python.

Programa 01

Escreva uma função, symbolsIn(word), que tem como entrada uma string e que devolve uma lista de símbolos. Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

EntradaResultado
"a_b_color_b_a"["a", "b", "color", "b", "a"]
"single"["single"]
""[""]
"_"["", ""]

Programa 02

Escreva uma função, alphabetFor(word), que tem como argumento uma string e que devolve o menor alfabeto para gerar essa palavra. Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

Note bem que no resultado não devem aparecer elementos repetidos.

EntradaResultado (sep="_")Resultado (sep="")
"a_b_color_b_a"["a", "b", "color"]["a", "_", "b", "c", "o", "l", "r"]
"single"["single"]["s", "i", "g", "l", "e"]
""[][]
"_"[]["_"]

Programa 03

Escreva uma função, generated(word, alphabet), em que word é uma string e alphabet uma lista de string e que determina se os símbolos de word estão todos em word (isto é, o resultado é booleano). Assuma que, por omissão, os símbolos da string são separados por underscore (_) mas, opcionalmente, a função tem o argumento sep para usar um separador alternativo.

Entrada wordEntrada alphabetResultado
"a_b_color_b_a"["a", "b", "color"]true
"single"["single"]true
""[]true

Programa 04

Use uma biblioteca de expressões regulares (do python3, por exemplo) e escreva expressões para reconhecer palavras que:

  1. Começam pela letra a; Não começam pela letra a; Terminam na letra a; Não terminam na letra a.
  2. Têm pelo menos uma ocorrência de a; Não têm ocorrências de a; O número de ocorrências de a não é 1; O número de ocorrências de a é exatamente 1.
  3. Têm um a ou um b; Têm um a e um b; Têm um a e, mais à frente, um b.
  4. Se têm um a então também têm um b; Se têm um a então também têm um b que ocorre antes do a; Se têm um a então também têm um b que ocorre depois do a; Se têm um a então não têm um b.

O pressuposto geral nas bibliotecas de ER é que vai ser feita uma pesquisa de subpalavras. Isto é, a ER é usada como um padrão que vai “percorrer” uma palavra “maior” para detetar subpalavras compatíveis com a ER dada.

Não é esse o pressuposto neste capítulo, onde as ER definem “palavras inteiras”.

Programa 05

  1. Escreva uma função countRE(expr, words) em que expr é uma das funções acima e words uma lista de string e que devolve o número de palavras em words aceites pela ER de expr.
  2. Repita este exercício para a função filterRE(expr, words) que devolve a lista das palavras em words aceites por expr. Re-escreva countRE = len(filterRE).
  3. Escreva o predicado allRE(expr, words) para testar se todas as palavras de words são aceites por expr. O mesmo para anyRE(expr, words) para testar se alguma palavra é aceite.

Programa 06

  1. Use os comandos grep para substituir a função filter acima e wc para substituir len.
  2. Aplique os filtros e contagens às palavras portuguesas com as ER dos exercícios anteriores.
  3. Quantas palavras têm cal depois de um v sem que ocorra um o no meio? Quais estão em comum com british_english?

Na linha de comandos, em geral, tem a seguinte documentação sobre cada comando, aqui ilustrado com grep:

  • grep -h ou grep --help, um resumo curto das principais operações.
  • man grep, uma “página” com uma descrição curta do comando e uma lista das operações (a.k.a cheat sheet).
  • info grep, um “livro” com a descrição completa do comando e operações.

Programa 07

Se observar as contagens de palavras portuguesas (no ficheiro portuguese):

  • Há 431114 palavras.
  • Das quais 355762 com a letra a
  • E 75352 em que a não ocorre.

Use o grep e o wc para obter exatamente estes três números.