Atividade 02 01

Prévia do material em texto

Aula 02.01 – linguagens Regulares 
1. Pode-se afirmar que a propriedade de fecho consiste em um conjunto de operações sobre 
as linguagens regulares que produzem uma nova linguagem também regular. Essas operações 
têm como intuito possibilitar a união, a interseção, a concatenação, entre outras operações 
sobre as linguagens regulares. 
Visto isso, considere as operações de união e concatenação. Assim, dadas as linguagens L1 = 
｛a, aaa, b｝, L2 = {bb, c} e L3 = {aa, cc, d} sobre o ∑ = {a, b, c, d}, informe qual é a linguagem 
obtida por L4 = ( L1 ∪ L2).L3 . 
 
Resposta incorreta. 
A. L4 = ｛aaa, acc, ad, aaaac, aaacc, aaadc, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd｝. 
 
Você acertou! 
B. L4 = ｛aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd｝. 
 
Considere L4 = ( L 1 ∪ L 2). L 3. 
Em um primeiro momento, obtém-se o resultado de (L 1 ∪ L 2) e, posteriormente, concatena-
se a L 3. Assim, tem-se: 
 L4 = ｛a, aaa, b, bb, c. {aa, cc, d} 
Por fim, deve-se concatenar o resultado da união de L 1 e L 2. 
Nesse sentindo, a resposta é dada por: 
L4 = {aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd} 
Perceba que, em nenhuma das linguagens, há o operador ε. Assim, este não aparecerá como 
parte da nova linguagem.
 
Resposta incorreta. 
C. L4 = ｛ε, aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd｝. 
 
Resposta incorreta. 
D. L4 = ｛ε, aaa, acc, ad, aaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, caa, ccc, cd｝. 
 
Resposta incorreta. 
E. L4 = ｛ε, a, aaa, b, bb, c, aaa, acc, ad, aaaaa, aaacc, aaad, baa, bcc, bd, bbaa, bbcc, bbd, 
caa, ccc, cd｝. 
 
 
2. Semelhante ao uso nas linguagens regulares, também é possível utilizar operadores 
diretamente nos símbolos, pois, dada uma Linguagem L = ｛a｝, se pode representá-la 
simplesmente por a. Desse modo, ao inserir o operador estrela, sobre a, por exemplo, 
teremos como resultado {ε, a, aa, aaa, ...}. 
 
Tendo em vista o exposto, dadas as linguagens a seguir, marque a opção que representa uma 
linguagem que produz uma cadeia que começa e termina com o mesmo símbolo, 
considerando que ∑={a, b}: 
 
Resposta incorreta. 
A. ∑ a*b*a*b* ∑. 
 
 
Resposta incorreta. 
B. ( ∑ ∑ )*. 
 
 
Resposta incorreta. 
C. b*a* ∑* a*b*. 
 
 
Você acertou! 
D. (a ∑* a) ∪ (b ∑* b) ∪ a ∪ b. 
 
A questão solicita uma linguagem que inicia e termina com o mesmo símbolo. Desse modo, 
considerando ∑=｛a,b｝, tem-se ( a ∑* a), no qual uma cadeia deve ser iniciada e terminada 
com o símbolo a e ∑* representa qualquer símbolo do alfabeto, inclusive ε. 
Seguindo o mesmo estilo, teremos (b ∑* b), no qual a cadeia deverá iniciar e terminar com o 
símbolo b. 
Por fim, deve-se considerar também a leitura dos símbolos a e b, em que terminam e começam 
com o mesmo símbolo. Assim, temos: 
(a ∑* a) ∪ (b ∑* b) ∪ a ∪ b 
 
 
Resposta incorreta. 
E. (a ∑* a) ∪ (b ∑* b). 
 
 
3. As operações de fechamento, ou operações de fecho, sob linguagens regulares, podem ser 
definidas como aquelas que, quando aplicadas a elas, produzem uma nova linguagem também 
regular. 
Considere as informações a seguir: 
Dada uma linguagem regular L = ｛00, 01, 11, 011｝ sob ∑ = {0, 1}. 
Analise as cadeias a seguir e informe quais fazem parte da linguagem L*: 
 
1- 00011100011 
2- 00111010000 
3- 11010001111 
4- 01101000100 
5- 11011110111 
 
Resposta incorreta. 
A. Fazem parte de L* as opções 1, 2 e 4. 
 
 
Resposta incorreta. 
B. Fazem parte de L* as opções 1, 3 e 5. 
 
 
Resposta incorreta. 
C. Fazem parte de L* as opções 3, 4 e 5. 
 
 
Resposta incorreta. 
D. Fazem parte de L* as opções 1, 4 e 5. 
 
 
Você acertou! 
E. Fazem parte de L* as opções 1, 3 e 4. 
 
Considerando a linguagem regular como L = ｛00, 01, 11, 011｝, tem-se que: 
1- 00011100011 = 00 01 11 00 011 
2- 00111010000 = 00 11 e regra quebrada em 1010000. 
3- 11010001111 = 11 01 00 011 11 
4- 01101000100 = 011 01 00 01 00 
5- 11011110111 = Podemos dividir em 
11 01 11 10 e regra quebrada em 111 ou 
11 011 11 011 e regra quebrada em 1. 
Portanto, estão corretas as opções 1, 3 e 4. 
 
 
4. Determinada linguagem regular L é formada por um conjunto de símbolos pertencentes a 
um alfabeto ∑. A partir dessa linguagem L, é possível obter um conjunto de cadeias que 
possibilitam elaborar um modelo computacional a ser aplicado em diversas situações, como, 
por exemplo, buscar determinados caracteres em um texto, fazer uma busca por meio de 
motores de buscas da web, entre outras. 
Considerando as linguagens apresentadas a seguir, relacione a primeira com a segunda 
coluna, verificando se cada cadeia obtida na segunda coluna pertence à da primeira. 
Posteriormente, marque o item que representa a ordem correta das linguagens reconhecidas. 
 
Considere ∑=｛1,0}. 
 
Primeira coluna: 
L1 = 1*∪ 0* 
L2 = 1 (01)* 0 
L3 = ∑*1∑*0∑*1∑* 
L4 = (ε ∪ 1) 0* 
 
Segunda coluna: 
( ) 0, 10, 100 
( ) 10, 1010, 101010 
( ) ε, 11, 00 
( ) 101, 11011, 101111 
A ordem correta obtida na segunda coluna é: 
 
Resposta incorreta. 
A. L4, L2, L3, L1. 
 
 
Resposta incorreta. 
B. L1, L2, L4, L3. 
 
 
Resposta incorreta. 
C. L2, L4, L3, L1. 
 
Você acertou! 
D. L4, L2, L1, L3. 
 
Nesta resolução, deve-se verificar cada cadeia do item e a qual linguagem ela pertence. Veja: 
( ) 0, 10, 100 
Ao analisar as linguagens, a primeira cadeia, 0, poderá fazer parte de L1 ou L4. Assim, deve-se 
analisar o valor seguinte. 
10 - pode pertencer à linguagem L1, L2 ou L4. Desse modo, passa-se para o passo seguinte. 
100 - este valor também pode pertencer a L1 ou L4. Dessa forma, considera-se que é possível 
ter L1 ou L4 para essa opção. 
( ) 10, 1010, 101010 
10 - como visto, pode pertencer a L1, L2 ou L4. 
1010 - esta cadeia é aceita por L2 e L3. 
101010 - esta cadeia também é aceita por L2 e L3. 
Desse modo, neste item, é possível afirmar que tem valor L2. 
( ) ε, 11, 00 
ε, apenas L1 e L4 aceitam ε como parte da linguagem. 
11 - apenas L1 aceita esta cadeia. 
00 - apenas L1 e L4 aceitam esta cadeia. 
Isto é, neste item, tem-se a linguagem L1. 
( ) 101, 11011, 101111 
101 - esta cadeia é aceita apenas por L3. 
11011 - esta cadeia é aceita por L3. 
101111 - esta cadeia é aceita apenas por L3. 
Desse modo, tem-se L4, L2, L1 e L3 como alternativa correta. 
 
Resposta incorreta. 
E. L3, L4, L1, L2. 
 
 
5. Verificar se uma linguagem é regular é fundamental, pois, em caso positivo, será possível 
solucionar determinado problema de forma simples e com tempo de execução ótimo. 
Existem algumas maneiras de verificar se uma linguagem é regular. Um exemplo é por meio 
do uso de AFDs. Por outro lado, há a possibilidade de verificar se dada linguagem é não 
regular. Para isso, uma das formas mais utilizadas é o lema do bombeamento. 
Com base Σ = ｛a, b｝, analise as linguagens a seguir e marque a opção referente a uma 
linguagem não regular. 
 
Resposta incorreta. 
A. L1 = ｛w | w inicia com b e termina com a｝. 
 
 
Resposta incorreta. 
B. L2 = ｛w | w possui um número de par de a e b｝. 
 
 
Resposta incorreta. 
C. L3 = ｛w | w possui aa ou bb como subcadeia｝. 
 
 
Resposta incorreta. 
D. L4 = ｛w | w possui aaa como sufixo｝. 
 
 
Você acertou! 
E. L5 = ｛w | w possui um número de a's igual ao número de b's}. 
 
Para a resolução desta questão, inicia-se pela forma mais simples, ou seja, por meio da tentativa 
da elaboração de um autômato finito que represente as linguagens. 
 
 
Quanto à linguagem L5, houve certa dificuldade em elaborar um autômato que a represente. 
Isso nos leva a ter indícios de que L5 não é uma linguagem regular. Desse modo, prova-se por 
meio do lema do bombeamento. 
Assumimos que L5 é uma linguagem regular. 
Desse modo, determinada cadeia w pode ser dividida em xyz. 
No qual y ≠ ε; 
|xy| <= p e 
xyiz ∈ L5 para todo i >= 0 
Considera-se a cadeia aaabbb e dividirmos em x = a, y = aa e z = bbb; ao bombear y, teremos 
uma cadeia como, por exemplo,aaaaabbb, o que torna a quantidade de a's diferente da 
quantidade de b's, tornando a linguagem não regular.