Atividade 02 02

Prévia do material em texto

AULA 02.02 – EXPRESSÕES REGULARES 
1. Determinada empresa Z pretende criar os e-mails institucionais de seus funcionários. Para 
isso, ela visa a fazer uso de expressões regulares. Assim, considerando uma cadeia 
qualquer w, faz-se necessário elaborar e-mails do tipo w@empresaZ.com, de forma que |w| 
tem tamanho mínimo igual a 1 e máximo igual a 4. 
Tendo em conta um alfabeto Σ = ｛a, b｝, um funcionário da empresa elaborou, então, uma 
expressão regular da seguinte forma 
(a + b)(ε + a + b)(ε + a + b)(ε + a + b). Tendo em vista o alfabeto, 
a expressão e as orientações dadas, informe quantas possibilidades existem para criação 
de e-mails. 
Resposta incorreta. 
A. 36.
 
Resposta incorreta. 
B. 48. 
 
Você acertou! 
C. 30. 
 
A partir da expressão (a + b)(ε + a + b)(ε + a + b)(ε + a + b), considerando 2 símbolos do 
alfabeto e, respectivamente, cadeias de tamanho 4, 3, 2 e 1, tem-se que: 
24 + 23 + 22 + 21 = 30 
Desse modo, é possível obter as seguintes cadeias: ｛a, b, aa, bb, ab, ba, aaa, aab, abb, aba, 
bbb, baa, bab, bba, aaaa, aaab, aabb, aaba, abbb, abab, abaa, abba, bbbb, bbba, bbaa, bbab, 
baaa, baba, babb, baab｝. 
 
Resposta incorreta. 
D. 26. 
 
Resposta incorreta. 
E. 46. 
 
2. Existem diversas maneiras de representar determinada linguagem regular, seja por 
autômatos finitos, seja por expressões regulares. Ao optar pela segunda, ainda assim, há 
diversas possibilidades capazes de originar uma mesma linguagem. 
Tendo em vista o informado e o alfabeto Σ = ｛0,1｝, considere a expressão 0 * (100) * (0 * 
(100) *) * e informe qual das opções a seguir produz o mesmo conjunto de cadeias: 
Você não acertou! 
A. (0100)* 
 
Resposta incorreta. 
B. (0100)*(0100)* 
 
Resposta incorreta. 
C. 0*1*0*0*0*1*0*0* 
 
Resposta incorreta. 
D. (0100)*+(0100)* 
 
Resposta correta. 
E. (0 + 100)* 
 
Considerando 0 * (100) * (0 * (100) *) *, é possível perceber que a expressão basicamente 
consiste em operações de concatenação e fechamento. 
É possível alterar a expressão dada por. 
(0 * (100) *) + (0 * (100) *) *. 
Ao analisar a expressão alterada, pode-se perceber que (0 * (100) *) e (0 * (100) *) * produzem 
as mesmas cadeias; assim, é possível excluir uma das extremidades. 
Ao escolher (0 * (100) *) *, resta (0 * (100) *), que pode ser transformada em (0 +100) *, 
produzindo, ainda assim, o mesmo conjunto de cadeias. 
 
 
 
3. As linguagens regulares podem ser denotadas por autômatos finitos ou expressões 
regulares. No primeiro caso, ou seja, com relação aos autômatos finitos, podem ser 
representadas por um conjunto de estados, um conjunto finito de símbolos, o qual 
chamamos de alfabeto, uma função de transição, um estado inicial e, por fim, apenas um ou 
um conjunto de estados finais. No segundo caso, as expressões regulares costumam ser 
representadas por um conjunto de símbolos de um alfabeto, símbolos que representam 
operações (concatenação, fecho estrela e união) e por parênteses, com o intuito de definir 
uma precedência. 
Há casos em que a representação de uma linguagem regular a partir de um autômato finito 
se torna a melhor opção, pois, de acordo com o problema, ela apresenta um formato de 
interpretação mais simples. No entanto, há momentos em que a expressão regular se torna 
indispensável. Desse modo, é possível converter um autômato finito em uma expressão 
regular. 
Tendo em vista o apresentado, analise o autômato a seguir e informe quais expressões 
regulares poderão denotar a mesma linguagem: 
 
Considere: 
I. (ab*a+ba*b)a*baa +(ab*a+ba*b)a*bbb 
II. (a+b)(b+a)*(a+b)a*b(a+b)(a+b) 
III. (ab*a + ba*b)a*b(aa + bb) 
IV. (ab*a)+(ba*+b)*ab(aa)+(bb) 
Entre as opções, estão corretas apenas: 
 
Resposta incorreta. 
A. I e II. 
 
Você acertou! 
B. I e III. 
 
Considerando o estado inicial do autômato, ao efetuar a leitura e ir para o estado q1 e, 
posteriormente, q5, tem-se que: ab*a. 
Em outro sentido, ao optar o caminho do estado q0 para q4 e, posteriormente, q5, temos que 
b*ab. Desse modo, obtém-se a primeira parte da expressão regular: 
(ab*a + ba*b). 
Dando sequência, no estado q5, temos a leitura de qualquer quantidade de a; assim, a* e, indo 
para q2, uma leitura obrigatória de b. Desse modo: 
(ab*a + ba*b)a*b. 
Nesse ponto, ao chegar a q2, há duas possibilidades. Seguir para o caminho q3 e 
posteriormente finalizar em q8, ou seguir a leitura para q6 e finalizar em q8. Desse modo, 
pode-se representar da seguinte maneira: 
(ab*a + ba*b)a*baa + (ab*a + ba*b)a*bbb 
ou 
(ab*a + ba*b)a*b(aa + bb). 
 
Resposta incorreta. 
C. II e III. 
 
Resposta incorreta. 
D. II e IV. 
 
Resposta incorreta. 
E. III e IV. 
 
 
 
4. As expressões regulares são uma maneira formal de descrever linguagens regulares a 
partir de conjuntos de símbolos e/ou caracteres especiais que formam determinada regra a 
partir de operadores de concatenação, união e fecho estrela. 
Dado o exposto, considerando um alfabeto Σ = ｛a, b｝ e uma linguagem L = {w ∈ Σ |(anbm) 
na qual n > 1 e m ≤ 1}, marque a alternativa que representa o complemento da linguagem 
dada por meio de uma expressão regular. 
Resposta incorreta. 
A. aa* + (b + ε). 
 
Resposta incorreta. 
B. (a + ε)*(b + ε). 
 
Resposta incorreta. 
C. (a*)bbb*. 
 
Resposta incorreta. 
D. (a + aa + aaa + ε)* b*. 
 
Você acertou! 
E. (a + ε)bbb*. 
O complemento é uma operação de fechamento sob linguagens regulares. Desse modo, 
quando aplicada a uma linguagem regular, essa expressão produz uma nova linguagem 
regular. 
Considerando n > 1 e m ≤ 1, o complemento são todos os valores que não correspondem a 
quantidade de a’s de no máximo 1 e uma quantidade de b’s de no mínimo 2. 
A partir do exposto, tem-se que: 
Para aa* + (b + ε), pode-se fazer uso da cadeia aaaaa, o que quebra a regra de n ≤ 1 e m > 1. 
Para (a + ε)*(b + ε), pode-se fazer uso da cadeia aaab, o que também quebra a regra n ≤ 1 e m 
> 1. 
Em (a*)bbb*, pode-se dispor de qualquer quantidade de a e, no mínimo, duas quantidades de 
b, o que também quebra a regra dada. 
Na expressão regular (a + aa + aaa + ε)* b*, pode-se fazer uso da cadeia bbbb, que também 
não corresponde à regra informada. 
Por fim, 
Para (a + ε)bbb* 
(a+ε), representa a leitura de apenas um ou nenhum a, ou seja, n ≤ 1 e bbb* torna obrigatória 
a leitura de ao menos dois b’s, isto é, m > 1. 
Desse modo, a opção correta é (a + ε)bbb*. 
 
 
5. As expressões regulares são utilizadas para denotar linguagens regulares. A partir delas, é 
possível fazer uso de operações de maneira bastante simples e sucinta. Quando utilizadas 
em linguagens de programação, normalmente são aplicadas com o intuito de verificar, por 
meio de determinada regra, se um conjunto de símbolos pertence a determinado padrão. 
Desse modo, pode-se inferir que estas podem ser utilizadas para verificar se determinada 
entrada corresponde a um padrão válido, como um e-mail. 
Dado o exposto, considerando um alfabeto Σ = ｛a, b｝ e uma expressão regular (a + b) * a 
(a + b) * a (a + b) *, marque a alternativa que melhor representa a expressão apresentada. 
 
Resposta incorreta. 
A. Conjunto de todas as cadeias que têm ao menos um b. 
 
Resposta incorreta. 
B. O conjunto de todas as cadeias contendo a subcadeia aa. 
 
Resposta incorreta. 
C. O conjunto de todas as cadeias contendo no máximo dois a’s. 
 
Você acertou! 
D. O conjunto de todas as cadeias contendo pelo menos dois a’s. 
 
Quanto às opções, tem-se: 
Conjunto de todas as cadeias que têm ao menos um b — perceba que é possível a elaboração 
da cadeia babab deste, o que torna essa afirmativa incorreta. 
O conjunto de todas as cadeias contendo a subcadeia aa — realmente há a possibilidade de 
formar cadeias de modo a existir a subcadeia aa; no entanto, tal qual citado anteriormente, a 
cadeia babab faz parte da linguagem, o que torna essa opção incorreta. 
O conjunto de todas as cadeias contendo no máximo dois a’s —a partir da expressão dada, é 
possível obter a cadeia aaaa, o que a torna incorreta. 
O conjunto de todas as cadeias contendo pelo menos dois a’s — de fato, a expressão torna 
obrigatória a leitura de pelo menos dois a’s: perceba em (a + b) * a (a + b) * a (a + b) *. 
O conjunto de todas as cadeias que começam e terminam com a ou b — perceba que, a partir 
do momento que existe a obrigatoriedade do uso de no mínimo dois a’s, essa afirmativa já se 
torna falsa, pois não é possível gerar a cadeia ab, por exemplo. 
 
Resposta incorreta. 
E. O conjunto de todas as cadeias que começam e terminam com a ou b.