Baixe o app para aproveitar ainda mais
Prévia do material em texto
16/04/2023, 13:29 Estácio: Alunos https://simulado.estacio.br/alunos/ 1/4 Teste de Conhecimento avalie sua aprendizagem Seja Σ={a,b}. Uma expressão regular denotando a linguagem L = {w∈Σ∗ tal que toda ocorrência de "a" em w é imediatamente seguida de "b"} é: TEORIA DA COMPUTAÇÃO Lupa Calc. CCT0832_A6_202107065796_V1 Aluno: JUCELINO COSTA DE OLIVEIRA Matr.: 202107065796 Disc.: TEORIA DA COMPUTAÇÃO 2023.1 EAD (G) / EX Prezado (a) Aluno(a), Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O mesmo será composto de questões de múltipla escolha. Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se familiarizar com este modelo de questões que será usado na sua AV e AVS. 1. b+(ab)∗ (a∗b)∗ (b+ab)∗ a∗b (ab)∗ Explicação: (A) (a∗b)∗ (B) (b+ab)∗ (C) a∗b (D) b+(ab)∗ (E) (ab)∗ As alternativas A e C estão incorretas, pois as expressões regulares reconhecem, por exemplo, a cadeia aab, que não faz parte da linguagem do enunciado. A alternativa E também está errada. O problema é que ela não reconhece todas as cadeias da linguagem do enunciado. Por exemplo, a cadeia bab faz parte de L, mas não é reconhecida pela ER. A alternativa D está errada. Entretanto, a ER dessa alternativa é confusa, pois não temos como saber se o operador "+" é o fecho positivo ou o operador de união, que é normalmente representado por "|". Felizmente, em ambos os casos a alternativa estaria errada. Portanto, a única alternativa correta é a B. javascript:voltar(); javascript:voltar(); javascript:diminui(); javascript:aumenta(); javascript:calculadora_on(); 16/04/2023, 13:29 Estácio: Alunos https://simulado.estacio.br/alunos/ 2/4 Seja o alfabeto ∑ constituído das 23 letras {a, b,c ...,z}. Se A= {legal, ruim} e B= {menino, menina} então o resultado de B concatenado A (B.A) será respectivamente: Considere as seguintes a�rmações sobre autômatos �nitos e expressões regulares: I A classe de linguagens aceita por um Autômato Finito Determinístico (AFD) não é a mesma que um Autômato Finito Não Determinístico (AFND). II Para algumas expressões regulares não é possível construir um AFD. III A expressão regular (b+ba)+ aceita os "strings" de b's e a's começando com b e não tendo dois a's consecutivos. Selecione a a�rmativa correta: Considere as seguintes expressões regulares cujo alfabeto é {a,b}. R1 = a(a ∪ b)* R2 = b(a ∪ b)* Se L(R) é uma linguagem associada a uma expressão regular R, é correto a�rmar que 2. {menino, menina, ruim, legal} {meninolegal, meninaruim, meninoruim, meninalegal} {meninolegal, meninalegal, meninoruim meninaruim} {legal, ruim, legallegal, legalruim, ruimruim, legallegal} {legal, ruim, menino, menina} Explicação: Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro conjunto. 3. As a�rmativas I e II são verdadeiras As a�rmativas I e III são verdadeiras As a�rmativas I e III são falsas Apenas a a�rmativa III é verdadeira As a�rmativas II e III são falsas Explicação: A primeira a�rmação é falsa porque AFDs e AFNDs reconhecem a mesma classe de linguagens (linguagens regulares). Além disso, essas duas classes de autômatos são equivalentes. A a�rmativa II também é falsa. Toda expressão regular representa uma linguagem regular que, consequentemente, é reconhecida por um AFD. Logo, é sempre possível construir um AFD para uma expressão regular. A a�rmativa III está correta. O único problema é a notação utilizada na expressão regular, que causa confusão. A ER pode ser escrita da seguinte forma: (b|ba)+. Observe que toda cadeia reconhecida pela ER inicia com b e que não é possível ter dois a's consecutivos. 4. 16/04/2023, 13:29 Estácio: Alunos https://simulado.estacio.br/alunos/ 3/4 Uma gramática G é de�nida por G=({x,y,z},{S,W,X,Y,Z},P,S) na qual os membros de P são S→WZW→X|YX→x|xXY→y|yYZ→z|zZ Qual das expressões regulares abaixo corresponde a esta gramática? Analise as seguintes igualdades de expressões regulares: I. a∗=(a∗)∗ II. (a+b)∗=(b+a)∗ III. a∗+b∗=(a+b)∗ A análise permite concluir que. L(R1) = L(r2) Um autômato �nito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados. Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem in�nita.2). Existe um autômato �nito determinístico cuja linguagem é igual a L(R1) ∪ L(R2). L(R2) = {w | w termina com b} Explicação: linguagem L(R1) é composta das palavras ou sequências que iniciam com ¿a¿ e a linguagem L(R2) é composta das palavras ou sequências que iniciam com ¿b¿. Note que a expressão regular (a ∪ b)* gera qualquer sequência de a´s e b´s. Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de L(R1) e L(R2) são todas as palavras que comecem com ¿a¿ ou com ¿b¿, ou seja qualquer palavra sobre o alfabeto, exceto a palavra vazia. Este AFD pode ser representado com dois estados apenas. Portanto, resta apenas a alternativa C, e como a�rmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R 5. xx∗(yy∗|zz∗) (xx∗|yy∗)zz∗ xx∗|yy∗|zz∗ (xx|yy)∗zz∗ xx∗yy∗zz∗ Explicação: Os símbolos não terminais X, Y e Z produzem, respectivamente, xx∗, yy∗ e zz∗. Além disso, podemos eliminar W substituindo-o na primeira produção: SXYZ→(X|Y)Z→xx∗→yy∗→zz∗ Substituindo X, Y e Z na primeira produção, obtemos Portanto a solução é S→(xx∗|yy∗)zz∗ 6. todas as igualdades são verdadeiras. nenhuma das igualdades é verdadeira. somente as igualdades I e II são verdadeiras. 16/04/2023, 13:29 Estácio: Alunos https://simulado.estacio.br/alunos/ 4/4 somente as igualdades II e III são verdadeiras. somente a igualdade I é verdadeira. Explicação: (A) somente as igualdades I e II são verdadeiras. (B) somente a igualdade I é verdadeira. (C) somente as igualdades II e III são verdadeiras. (D) todas as igualdades são verdadeiras. (E) nenhuma das igualdades é verdadeira. Resolução Nas a�rmativas II e III o operador "+" não é o fecho positivo e sim o operador de união. Podemos reescrever as a�rmativas da seguinte forma: II. (a|b)∗=(b|a)∗ III. a∗|b∗=(a|b)∗ A a�rmativa I está correta (é trivial). A a�rmativa II também está correta (também é trivial, pois o operador de união "|" é comutativo). A a�rmativa III está errada. Enquanto a expressão regular à esquerda reconhece cadeias contendo apenas a's ou cadeias contendo apenas b's, a expressão regular à direita reconhece qualquer cadeia de a's e b's. Por exemplo, a cadeia aab é reconhecida por (a|b)∗, mas não é reconhecida por a∗|b∗. Portanto, a alternativa correta é a A. Não Respondida Não Gravada Gravada Exercício inciado em 16/04/2023 13:28:45. javascript:abre_colabore('35479','306275212','6186062297');
Compartilhar