Linguagens Formais e Automatos_Questionario 1

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere o autômato finito indicado na imagem, no qual o estado inicial é o estado 0 e o 
estado final é o estado 1. Este autômato é o reconhecedor de uma Linguagem Regular. Ao 
executá-lo tendo como entrada a cadeia "klnl", a execução irá terminar no estado: 
 
 
Resposta Selecionada: b. 
2. 
Respostas: a. 
1. 
 b. 
2. 
 c. 
3. 
 d. 
4. 
 e. 
5. 
Comentário da 
resposta: 
Resposta: B 
Comentário: as transições de estados ao percorrer a cadeia dada 
serão, respectivamente, 1, permanece em 1, 3 e 2. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Uma gramática pode ser representada por um conjunto de 
parâmetros. Assinale a alternativa que não indica corretamente um 
dos parâmetros constituintes de uma gramática: 
 
Resposta 
Selecionada: 
d. 
N: conjunto das cadeias que podem ser definidas 
pela gramática. 
Respostas: a. 
P: conjunto das regras de substituição que 
constituem a gramática. 
 
b. 
V: conjunto dos símbolos terminais do alfabeto da 
gramática. 
 c. 
S: símbolo não terminal raiz da gramática. 
 
d. 
N: conjunto das cadeias que podem ser definidas 
pela gramática. 
 e. 
 
Σ: conjunto dos símbolos não terminais do alfabeto 
da gramática. 
Comentário da 
resposta: 
Resposta: D 
Comentário: uma gramática é definida por quatro 
parâmetros, V, Σ, P e S, que correspondem às 
descrições resumidas das demais alternativas da 
questão. 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
Considere a Linguagem Regular definida pela gramática a seguir, 
sendo S a raiz: 
 
V = {1, 2, 3} 
Σ = {S, A, C} 
P= {S → 
1S, S → A, A → 23C, A → 33C, A → 
3C, C → 1C, C → ε} 
 
Qual das cadeias a seguir não pertence a esta linguagem? 
 
Resposta Selecionada: d. 
13331111. 
Respostas: a. 
1113. 
 b. 
133. 
 c. 
1111311. 
 d. 
13331111. 
 e. 
3. 
Comentário da 
resposta: 
Resposta: D 
Comentário: se observarmos a quarta e quinta regras 
de substituição, as cadeias formadas terão apenas um 
ou dois símbolos “3”. Assim, uma cadeia com três “3” 
não pode ser formada. 
 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Considere a Linguagem Regular L definida pela expressão regular L = 
x*(y+z)x(y)*. Qual das cadeias a seguir não pertence a esta 
linguagem? 
 
Resposta Selecionada: b. 
xyxxy. 
Respostas: a. 
xzx. 
 b. 
xyxxy. 
 c. 
xyxy. 
 d. 
zx. 
 e. 
xxyxy. 
Comentário 
da resposta: 
Resposta: B 
Comentário: as cadeias formadas por esta expressão 
regular terão o formato "(0 ou mais x)yx(0 ou mais y)" ou 
formato "(0 ou mais x)zx(0 ou mais y)". A cadeia xyxxy é 
a única que não corresponde a u7m destes dois 
formatos. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Considere o Fecho de Kleene indicado por (9+8)* e assinale a 
alternativa correta: 
 
Resposta 
Selecionada: 
a. 
Este fechamento pode gerar cadeias que comecem 
com o símbolo 9 ou com o símbolo 8. 
Respostas: a. 
Este fechamento pode gerar cadeias que comecem 
com o símbolo 9 ou com o símbolo 8. 
 
b. 
Não é possível gerar a cadeia vazia a partir deste 
fechamento. 
 
c. 
Apenas cadeias que comecem com o símbolo 9 podem 
ser geradas a partir deste fechamento. 
 
d. 
Apenas cadeias que comecem com o símbolo 8 podem 
ser geradas a partir deste fechamento. 
 
 
e. 
Em qualquer cadeia não vazia gerada por este 
fechamento, teremos sempre um símbolo 8 
imediatamente na sequência de todo símbolo 9. 
Comentário da 
resposta: 
Resposta: A 
Comentário: esta expressão regular permite gerar 
qualquer combinação possível dos símbolos 8 e 9, em 
qualquer ordem, incluindo uma cadeia vazia (zero 
símbolos 8 e 9). 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Analise as afirmações a seguir acerca de Gramáticas Regulares: 
 
I. Toda Gramática regular à direita possui suas regras de substituição 
como sendo a substituição de um símbolo não terminal por um 
símbolo terminal ou por um par não terminal/terminal, nesta ordem. 
II. Toda Gramática regular à esquerda possui suas regras de 
substituição como sendo a substituição de um símbolo não terminal 
por um símbolo terminal ou por um par terminal/não terminal, nesta 
ordem. 
III. Toda Gramática Linear à esquerda possui uma gramática 
equivalente à direita e vice-versa. 
 
Estão corretas as afirmações: 
 
Resposta Selecionada: c. 
III, apenas. 
Respostas: a. 
I e II, apenas. 
 b. 
I e III, apenas. 
 c. 
III, apenas. 
 d. 
II e III, apenas. 
 e. 
I, II e III. 
Comentário da 
resposta: 
Resposta: C 
Comentário: as definições das gramáticas nas 
afirmações I e II estão invertidas, a I descreve 
gramáticas à esquerda e a II, gramáticas à direita. 
 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Em 1959, Noam Chomsky apresentou uma hierarquia das Linguagens, a qual leva seu 
nome (Hierarquia de Chomsky). Indique a alternativa em relação a esta hierarquia: 
Resposta 
Selecionada: 
e. 
As Linguagens de Programação normalmente se encontram em formas 
que correspondem aos Tipos 2 e 3 da Hierarquia. 
Respostas: a. 
As Linguagens Humanas (Linguagens Naturais) são classificadas como 
o Tipo 3, por serem as mais complexas. 
 
b. 
A maioria das Linguagens de Programação encontram-se no Tipo 1, 
que correspondem às Linguagens Irrestritas. 
 
c. 
As Linguagens Regulares são do tipo 2, por serem mais complexas que 
as Linguagens Livres de Contexto. 
 
d. 
Na prática, o tipo mais restrito de Linguagens, as de tipo 3, acabam por 
não existirem, sendo apenas uma ferramenta teórica. 
 
e. 
As Linguagens de Programação normalmente se encontram em formas 
que correspondem aos Tipos 2 e 3 da Hierarquia. 
Comentário da 
resposta: 
Resposta: E 
Comentário: as Linguagens de Programação, na sua maioria, são 
Regulares ou Livres de Contexto. Linguagens Naturais são do Tipo I. A 
imagem a seguir mostra esta hierarquia: 
 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Sabendo que o autômato finito da imagem possui estado inicial igual a 0, e estados finais 
iguais a 0 e 1, a gramática regular que ele verifica é: 
 
 
Resposta Selecionada: e. 
(a+b)*(c+d)*. 
Respostas: a. 
(c+d)* (a+b)*. 
 b. 
(a+b)*ca. 
 c. 
(a+b)(c+d)*. 
 d. 
(a)*(c+d)*. 
 e. 
(a+b)*(c+d)*. 
 
Comentário da 
resposta: 
Resposta: E 
Comentário: a primeira transição de 0 para 0 representa (a+b)*. A 
transição de 0 para 1 e de 1 para 1 identificam (c+d)*. 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Sabendo que o autômato finito da imagem possui estado inicial igual a 0 e estado final 
igual a 2, ao analisarmos a cadeia 0322222, podemos concluir que ela: 
 
 
Resposta Selecionada: a. 
Será aceita, terminando no estado 2. 
Respostas: a. 
Será aceita, terminando no estado 2. 
 b. 
Será rejeitada, terminando no estado 2. 
 c. 
Será rejeitada, terminando no estado 1. 
 d. 
Será rejeitada, terminando no estado 0. 
 e. 
Será rejeitada, terminando no estado 3. 
Comentário da 
resposta: 
Resposta: A 
Comentário: as transições de estado para cada símbolo da cadeia serão 
respectivamente: 1,1, 2, 2, 2, 2, 2 (estado final de aceitação). 
 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Considere a Linguagem Regular definida pela gramática a seguir, 
sendo S a raiz: 
 
V = {p, q, r} 
Σ = {S, A, C} 
P= {S → pS, S → A, A → qqB, B → rB, B → ε} 
 
A expressão regular correspondente é: 
 
Resposta Selecionada: e. 
p*qqr*. 
Respostas: a. 
p*qr*. 
 b. 
pq*r. 
 c. 
 
pqr. 
 d. 
pqqr. 
 e. 
p*qqr*. 
Comentário da 
resposta: 
Resposta: E 
Comentário: as duas primeiras regras de transição 
indicam um fechamento de p; a segunda indica uma 
concatenação de dois q´s; e, por fim, as duas últimas 
indicam um fechamento de r.