2

2.1 Exercícios propostos

1. Descreva informalmente (por palavras) as linguagens representadas pelas seguintes expressões: Considerando o alfabeto Σ = {0,1}:
a) 0(0|1)*0
L(A) = {u ∈ Σ*:u todas as palavras começadas por zero e terminados em zero}
b) (01)* L(A) = {u ∈ Σ*:u zero ou mais ocorrências da expressão 01}
c) (0|1)*0(0|1)(0|1)
L(A) = {u ∈ Σ*:u todas as palavras com três ou mais símbolos cujo o terceiro da direita para a esquerda é zero}
d) 0*10*10*10* L(A) = {u ∈ Σ*:u qualquer palavra com exatamente três uns}
e) (0|1)*111(0|1)* L(A) = {u ∈ Σ*:u qualquer palavra com três uns precedidos }

2. Considerando o alfabeto Σ = {A, B, C, . . . , Z, a, b, c, . . . , z}, represente as seguintes linguagens utilizando expressões regulares:

a) L(A) = {u ∈ Σ*:u tem pelo menos dois a's juntos}
Σ*[aA][aA] Σ*
b) L(A) = {u ∈ Σ*:u tem comprimento inferior a 4}
[a-zA-Z]{0,3} ou Σ{0,3}
c) L(A) = {u ∈ Σ*:u começa por uma maiúscula}
[A-Z] Σ*[
d) L(A) = {u ∈ Σ*:u tem um número par de maiúsculas e um número ímpar de minúsculas, e tem comprimento múltiplo de 4}
Impossível !!!

3. Diga se são verdadeiras ou falsas as seguintes afirmações:

a) (0|1)* ⇔ (0*|1*)
Falso
b) (0|1)* ⇔ (0*1*)*
Verdadeiro (0|1)* ⇔ (0*|1*)*

4. Considerando o alfabeto Σ = {0,1}, represente as seguintes linguagens utilizando expressões regulares:

a) L(A) = {u ∈ Σ*: u é um número binário múltiplo de 4}

(0|1)* 00

b) L(A) = {u ∈ Σ*:111 não é factor de u}

(0|10|110)*(1|11|ԑ)  (1?1?0)*1?1?

c) L(A) = {u ∈ Σ*: u tem um número par de 1's}
0*110*
d) L(A) = {u ∈ Σ*:u é vazia ou tem dígitos todos iguais, sendo de comprimento par as sequências de 0's, e ímpar as sequências de 1's}
Σ|00+1(11)*

e) L(A) = {u ∈ Σ*:u é múltiplo de 4 mas não de 8}
(0|1)*100
f) L(A) = {u ∈ Σ*:u tem comprimento 3}
(0|1){3}

5. Para a classificação dos alunos de uma escola, cada nota encontra-se codificada através do par: NT, em que N é um valor inteiro entre 0 e 20 e T pode ser a letra F, ou E ou o par de letras RF.