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.

• Palavras, Linguagens e Expressões Regulares — Exercícios
  • Alfabetos, Palavras e Linguagens
    • Exercício 01
    • Exercício 02
    • Exercício 03
    • Exercício 04
    • Exercício 05
    • Exercício 06
    • Exercício 07
    • Exercício 08
    • Exercício 09
    • Exercício 10
    • Exercício 11
    • Exercício 12
    • Exercício 13
    • Exercício 14
    • Exercício 15
  • Expressões Regulares
    • Exercício 16
    • Exercício 17
    • Exercício 18
    • Exercício 19
    • Exercício 20
    • Exercício 21
    • Exercício 22
    • Exercício 23
    • Exercício 24
    • Exercício 25
    • Exercício 26
    • Exercício 27
  • Implementação
    • Programa 00
    • Programa 01
    • Programa 02
    • Programa 03
    • Programa 04
    • Programa 05
    • Programa 06
    • Programa 07

Alfabetos, Palavras e Linguagens

Exercício 01

1. Defina alfabetos para:
   1. Escrever os números naturais $0,1,2,\dots$ 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 =\left\{0,1,2\right\}$ 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^{0}u$
   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 =\left\{0,1,2,3\right\}$:

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

Exercício 03

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

1. $C_1=\left\{\text{palavras sobre }\Sigma \text{ tais que o sıˊmbolo }a\text{ ocorre aos pares}\right\}$. $C_1$ inclui, por exemplo, $bbaab$ e $aaaa$ mas não inclui $aaa$ nem $aabaaaba$.
2. $C_2=\left\{p\in {\Sigma }^{\ast }:\left|p\right|\text{ eˊ par },p\text{ comec¸a por }a\text{ e, em }p\text{, os }a\text{ e os }b\text{ ocorrem alternados}\right\}$.
3. $C_3=\left\{p\in {\Sigma }^{\ast }:p\text{eˊ capicua}\right\}$.
4. ✓ $C_4=\left\{a^n{b}^n\in {\Sigma }^{\ast }:n>0\right\}$.
5. $C_5=\left\{a^i{b}^j\in {\Sigma }^{\ast }:0\le i<j\right\}$.
6. ✓ $C_6=\left\{p\in {\Sigma }^{\ast }:{\left|p\right|}_a={\left|p\right|}_b\right\}$. Sugestão: Use a concatenação no passo recursivo.

Exercício 04

Encontre a menor palavra sobre o alfabeto $\Sigma =\left\{0\right\}$ que não está em ${\left\{\lambda ,0,0^2,0^5\right\}}^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. $\left\{0^n:n\text{eˊ par}\right\}$.
2. $\left\{p\in {\left\{0,1\right\}}^{\ast }:\left|p\right|\le 4\right\}$.
3. $\left\{0^n{1}^n:n\ge 0\right\}$.
4. $\left\{0^n{1}^m:n,m\ge 0\right\}$.

Exercício 08

Descreva recursivamente o conjunto das palavras sobre o alfabeto $\left\{a,b\right\}$...

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 $\left\{0,1\right\}\left\{1,2\right\}$ e compare com $\left\{1,2\right\}\left\{0,1\right\}$. Enuncie o que observou como uma propriedade geral das operações de linguagens.
2. É verdade que $\left|AB\right|=\left|A\right|\left|B\right|$?
3. Sejam $A=\left\{(01{)}^n:n\ge 0\right\}$ e $B=\left\{01,010\right\}$. Calcule $AB$ e $ABA$.
4. Verifique que ${\left\{0,10\right\}}^{\ast }$ é a linguagem das palavras binárias que não têm $11$ como subpalavra e que terminam em $0$.
5. † Confirme que $A^{+}=A^{\ast }$ se e só se $\lambda \in A$.
6. † Confirme que ${\left(AB\right)}^R=B^R{A}^R$ e que ${\left(A\cup B\right)}^R=A^R\cup B^R$.

Exercício 10

Mostre que, se $A,B$ forem linguagens então ${\left(A\cup B\right)}^{\ast }=A^{\ast }{\left(B{A}^{\ast }\right)}^{\ast }$.

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=\left\{\mathtt{anti},\mathtt{pro},\lambda \right\},B=\left\{\mathtt{pesso},\mathtt{soci}\right\},C=\left\{\mathtt{al}\right\}$. O que são $ABC$ e $A^{\ast }BC$?

Exercício 12

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

Exercício 13

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

1. ${A^R}^{\ast }={\left(A^{\ast }\right)}^R$.
2. ${\left(A^{+}\right)}^{\ast }=A^{\ast }$.
3. ${\left(A\cup A^R\right)}^{\ast }=A^{\ast }\cup {\left(A^{\ast }\right)}^R$.
4. $A^2\cup B^2={\left(A\cup B\right)}^2$.
5. $A^{\ast }\cap B^{\ast }={\left(A\cap B\right)}^{\ast }$.

Exercício 14

Mostre que para $n\ge 1$:

1. ${\bigcup }_{i=0}^n{A}^i={\left(\left\{\lambda \right\}\cup A\right)}^n$.
2. ${\left(A^{\ast }\right)}^n=A^{\ast }$.
3. Se $\lambda \notin A$ então $\left(A^{+}\right)=A^n{A}^{\ast }$.

Exercício 15

Demonstre as seguintes igualdades:

1. $A{\left(BA\right)}^{\ast }={\left(AB\right)}^{\ast }A$.
2. ${\left(A\cup B\right)}^{\ast }={\left(A^{\ast }{B}^{\ast }\right)}^{\ast }$.
3. $A\left(B\cup C\right)=AB\cup AC$.
4. $\left(A\cup B\right)C=AC\cup BC$.
5. $A^{\ast }B{\left(D{A}^{\ast }B\cup C\right)}^{\ast }={\left(A\cup B{C}^{\ast }D\right)}^{\ast }B{C}^{\ast }$.

Expressões Regulares

Exercício 16

✓ Considere a expressão regular ${\left(11\cup 0\right)}^{\ast }{\left(00\cup 1\right)}^{\ast }$ e o respetivo diagrama.

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

Exercício 17

1. Desenhe e simplifique o diagrama de $a^{\ast }b{\left(c\cup d{a}^{\ast }\right)}^{\ast }$.
2. Encontre a mais curta palavra não vazia das linguagens das seguintes expressões:
   1. $10\cup \left(0\cup 11\right)0^{\ast }1$.
   2. ${\left(00\cup 11\cup \left(01\cup 10\right){\left(00\cup 11\right)}^{\ast }\left(01\cup 10\right)\right)}^{\ast }$.
   3. ${\left({\left(00\cup 11\right)}^{\ast }\cup {\left(001\cup 110\right)}^{\ast }\right)}^{\ast }$.
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. $\left(00\cup 10\right){\left(101\right)}^{\ast }\cup 01$.
   2. ${\left({\left(00\cup 11\right)}^{\ast }\cup {\left(001\cup 110\right)}^{\ast }\right)}^{\ast }$.
   3. ${\left(a\cup b{c}^{\ast }d\right)}^{\ast }b{c}^{\ast }$.

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

      

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

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

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 $\left\{a,b,c\right\}$ 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 $\left\{a,b,c\right\}$ de comprimento inferior a 3.
4. As palavras sobre $\left\{a,b,c\right\}$ que começam por $a$, acabam em $cc$ e têm exatamente dois $b$'s.
5. A linguagem das palavras sobre $\left\{a,b\right\}$ que têm $aa$ e $bb$ como subpalavras.
6. As palavras sobre $\left\{a,b\right\}$ de que $bba$ não é subpalavra.
7. ✓ A linguagem das palavras sobre $\left\{a,b\right\}$ que não têm prefixo $aaa$.
8. ✓ A linguagem das palavras sobre $\left\{a,b\right\}$ que não têm $aaa$ como subpalavra.
9. As palavras sobre $\left\{a,b\right\}$ em que $ab$ não ocorre.
10. As palavras sobre $\left\{a,b\right\}$ em que $ab$ ocorre.
11. As palavras sobre $\left\{a,b\right\}$ 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. ✓ ${\varnothing }^{\ast }\cup a^{\ast }\cup b^{\ast }(a\cup b{)}^{\ast }$
2. $a{a}^{\ast }b\cup b$
3. ✓ $b^{\ast }(a\cup (b^{\ast }{a}^{\ast }{)}^{\ast })a{b}^{\ast }(a{b}^{\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{array}{rl}{0}^{\ast }{\left(0\cup 1\right)}^{\ast }& ={\left(0\cup {10}^{\ast }\right)}^{\ast }\\ {\left(10\right)}^{+}\left(0^{\ast }{1}^{\ast }\cup 0^{\ast }\right)& ={\left(10\right)}^{\ast }{10^{+}1}^{\ast }\end{array}$$

Exercício 25

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

   1. ${\left(0^{\ast }{1}^{\ast }\right)}^{\ast }0$.
   2. ${\left({01}^{\ast }\right)}^{\ast }0$.
   3. ${\left(00\cup 11\cup \left(01\cup 10\right){\left(00\cup 11\right)}^{\ast }\left(01\cup 10\right)\right)}^{\ast }$.
   4. $0^{\ast }\cup \left(0^{\ast }1\cup 0^{\ast }11\right){\left(0^{+}1\cup 0^{+}11\right)}^{\ast }{0}^{\ast }$.

2. Simplifique as seguintes expressões regulares:

   1. ${\left(00\right)}^{\ast }0\cup \left(00^{\ast }\right)$.
   2. $\left(0\cup 1\right){\left(\lambda \cup 00\right)}^{+}\cup \left(0\cup 1\right)$.
   3. $\left(0\cup \lambda \right)0^{\ast }1$.

3. Mostre que ${\left(0^2\cup 0^3\right)}^{\ast }={\left(0^2{0}^{\ast }\right)}^{\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.

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.

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.

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.