Logo Passei Direto
Buscar

CCT0832 - Teste de conhecimento - Aula 6

Ferramentas de estudo

Questões resolvidas

Uma gramática G é definida 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?
xx∗yy∗zz∗
xx∗|yy∗|zz∗
xx∗(yy∗|zz∗)
(xx|yy)∗zz∗
(xx∗|yy∗)zz∗

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 afirmar que:
L(R2) = {w | w termina com b}
L(R1) = L(r2)
Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.

Analise as seguintes igualdades de expressões regulares:
A análise permite concluir que.
I. a∗=(a∗)∗
II. (a+b)∗=(b+a)∗
III. a∗+b∗=(a+b)∗
somente a igualdade I é verdadeira.
nenhuma das igualdades é verdadeira.
somente as igualdades II e III são verdadeiras.
todas as igualdades são verdadeiras.
somente as igualdades I e II são verdadeiras.

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:
{legal, ruim, menino, menina}
{menino, menina, ruim, legal}
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
{meninolegal, meninaruim, meninoruim, meninalegal}
{meninolegal, meninalegal, meninoruim meninaruim}

Considere as seguintes afirmacoes sobre autômatos finitos e expressões regulares:
Selecione a afirmativa correta:
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.
As afirmativas I e II são verdadeiras
As afirmativas I e III são falsas
Apenas a afirmativa III é verdadeira
As afirmativas II e III são falsas
As afirmativas I e III são verdadeiras

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'}.
É:
(ab)∗
b+(ab)∗
(b+ab)∗
(a∗b)∗
a∗b

Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Questões resolvidas

Uma gramática G é definida 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?
xx∗yy∗zz∗
xx∗|yy∗|zz∗
xx∗(yy∗|zz∗)
(xx|yy)∗zz∗
(xx∗|yy∗)zz∗

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 afirmar que:
L(R2) = {w | w termina com b}
L(R1) = L(r2)
Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.

Analise as seguintes igualdades de expressões regulares:
A análise permite concluir que.
I. a∗=(a∗)∗
II. (a+b)∗=(b+a)∗
III. a∗+b∗=(a+b)∗
somente a igualdade I é verdadeira.
nenhuma das igualdades é verdadeira.
somente as igualdades II e III são verdadeiras.
todas as igualdades são verdadeiras.
somente as igualdades I e II são verdadeiras.

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:
{legal, ruim, menino, menina}
{menino, menina, ruim, legal}
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
{meninolegal, meninaruim, meninoruim, meninalegal}
{meninolegal, meninalegal, meninoruim meninaruim}

Considere as seguintes afirmacoes sobre autômatos finitos e expressões regulares:
Selecione a afirmativa correta:
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.
As afirmativas I e II são verdadeiras
As afirmativas I e III são falsas
Apenas a afirmativa III é verdadeira
As afirmativas II e III são falsas
As afirmativas I e III são verdadeiras

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'}.
É:
(ab)∗
b+(ab)∗
(b+ab)∗
(a∗b)∗
a∗b

Prévia do material em texto

1
        Questão
	
	
	Uma gramática G é definida 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?
		
	
	xx∗(yy∗|zz∗)
	
	(xx|yy)∗zz∗
	
	 xx∗|yy∗|zz∗
 
	 
	(xx∗|yy∗)zz∗
	
	 xx∗yy∗zz∗
	Respondido em 15/03/2021 16:28:46
	
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∗   
	
	
	 
		2
        Questão
	
	
	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 afirmar que
 
		
	
	L(R2) = {w | w termina com b}
	
	Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
 
 
	 
	Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
	
	L(R1) = L(r2) 
	
	Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.2). 
	Respondido em 15/03/2021 17:00:00
	
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 afirmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R
	
	
	 
		3
        Questão
	
	
	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.
		
	
	somente a igualdade I é verdadeira.
	 
	somente as igualdades I e II são verdadeiras.
 
	
	nenhuma das igualdades é verdadeira.
	
	todas as igualdades são verdadeiras.
	
	somente as igualdades II e III são verdadeiras.
	Respondido em 15/03/2021 17:01:45
	
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 afirmativas II e III o operador "+" não é o fecho positivo e sim o operador de união. Podemos reescrever as afirmativas da seguinte forma:
II. (a|b)∗=(b|a)∗
III. a∗|b∗=(a|b)∗
A afirmativa I está correta (é trivial).
A afirmativa II também está correta (também é trivial, pois o operador de união "|" é comutativo).
A afirmativa 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.
	
	
	 
		4
        Questão
	
	
	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:
		
	 
	{meninolegal, meninalegal, meninoruim meninaruim}
	
	{legal, ruim, menino, menina}
	
	{menino, menina, ruim, legal}
	
	{meninolegal, meninaruim, meninoruim, meninalegal}
	
	{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
	Respondido em 15/03/2021 17:03:08
	
Explicação:
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro conjunto. 
	
	
	 
		5
        Questão
	
	
	Considere as seguintes afirmações sobre autômatos finitos 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 afirmativa correta:
		
	
	As afirmativas II e III são falsas
	
	As afirmativas I e III são verdadeiras
 
	
	As afirmativas I e III são falsas
	
	As afirmativas I e II são verdadeiras
	 
	Apenas a afirmativa III é verdadeira
	Respondido em 15/03/2021 17:04:12
	
Explicação:
A primeira afirmaçã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 afirmativa 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 afirmativa 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.
	
	
	 
		6
        Questão
	
	
	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"} é:
		
	 
	(b+ab)∗
	
	(ab)∗
 
	
	 b+(ab)∗
	
	 a∗b
	
	(a∗b)∗
	Respondido em 15/03/2021 17:04:55
	
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.

Mais conteúdos dessa disciplina