AV_TEORIA_DA_COMPUTAÇÃO

Prévia do material em texto

1. 
Ref.: 6101939 Pontos: 1,00 / 1,00 
Seja G = (V, T, P, E), onde V = {+, *, (, ), id, T, F, E}, T = {+, *, (, ), id} e P: 
 
1. E → E + T 4. T → F 
2. E → T 5. F → (E) 
3. T → T * F 6. F → id 
 
Os símbolos E, T, F são abreviaturas para expressão, termo e fator, respectivamente e id é um identi cador válido dessa 
linguagem. 
 
Assinale a alternativa que tem uma derivação correta para a expressão id + (id * id): 
 T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id / (id - id). 
E =>1 E + T =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F * F) =>6 id + (id * id). 
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id). 
E =>1 E + T =>3 E + T * F =>5 E + T * (E) =>1 E + T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id). 
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>4 (F + F*F) =>6 (id + id *id). 
 
 2. Ref.: 6101772 
 Pontos: 1,00 / 1,00 
Considere a seguinte gramática: G = {S, (0, 1, c), (S→0S0, S→1S1, S→c), S}. Assinale a alternativa que contém, apenas, 
cadeias geradas por essa gramática. 
 00c00, 1100011, 00100, c 
 0c0, 110c111, 001c100, c 
 00c1, 001c100, 00c10, c 
0c0, 11c11, 001c100, c 
00c10, 11c11, 01c11, c 
 
 
 
 
 3. Ref.: 6096597 
 Pontos: 1,00 / 1,00 
 
 
 
 
Considere o autômato nito mostrado na gura abaixo (os círculos concêntricos representam estado nal) e assinale 
a a rmativa correta. 
 
 A palavra 10101 é reconhecida pelo autômato. 
 A palavra 01010 não é reconhecida pelo autômato. 
A palavra vazia é reconhecida pelo autômato. 
A palavra vazia não é reconhecida pelo autômato. 
A palavra 101 é reconhecida pelo autômato. 
 
 
(POSCOMP / 2009) Qual é a linguagem da gramática com as seguintes regras de produção: 
S → ASb | c 
A → a 
 {acbn|n ∈ N} 
 {ancnb|n ∈ N} 
 {acnb|n ∈ N} 
 {ancbn|n ∈ N} 
 {ancb|n ∈ N} 
 
 
(POSCOMP / 2008) Seja o autômato nito mostrado na gura abaixo que opera sobre o alfabeto Σ = {a,b} (o círculo em 
negrito indica um estado terminal): 
 
Analise as seguintes a rmativas. 
I. O autômato nito mostrado na gura é determinístico. 
II. O autômato nito mostrado na gura é não-determinístico. 
 
 
 
 
III. O autômato nito mostrado na gura reconhece a palavra vazia 
A análise permite concluir que 
 Somente as a rmativas I e II são falsas. 
 Somente a a rmativa II é falsa. 
 Somente a a rmativa III é falsa. 
Somente a a rmativa I é falsa. 
Somente as a rmativas II e III são falsas. 
 
 
 
 
 6. Ref.: 6097522 Pontos: 1,00 / 1,00 
(POSCOMP / 2008) Considere a seguinte gramática G, onde S é o símbolo inicial: 
 S → AcB 
A → cA | aB 
B → cB | aA 
 A → λ 
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G. 
 aaca 
aa 
aaaca 
ccac 
 ccca 
 
 
Ref.: 6097520 7. Pontos: 1,00 / 1,00 
Se ∑ = {1}, então ∑* - ∑+ é 
 λ 
{1} 
{λ, 1, 11¿..} 
1+ 
1* 
 
 
 
 
 8. Ref.: 6113811 Pontos: 1,00 / 1,00 
 Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky 
e suas respectivas máquinas reconhecedoras, analise as a rmações a seguir e assinale a falsa. 
 
 Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = , é indecidível. 
 
 
 
 
 Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2). 
 O problema da parada de uma máquina de Turing é indecidível. 
 Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina 
de Turing. 
 É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par. 
 
 9. Ref.: 6113721 
 Pontos: 1,00 / 1,00 
Considere dois problemas de decisão PA e PB, sendo PA indecidível e PB decidível. Observe também dois problemas de 
decisão PC e PD, cuja decidibilidade é desconhecida. Suponha que seja possível construir de forma correta as seguintes 
reduções: 
· de PA para PC. 
· de PD para PA. 
· de PD para PB. 
Com base no cenário descrito, assinale a alternativa correta. 
 
PC é indecidível e PD é decidível. 
Não se pode a rmar nada sobre a decidibilidade dos problemas PC e PD. 
PC e PD são ambos indecidíveis. 
PC é indecidível, contudo não se pode a rmar nada sobre a decidibilidade de PD. 
Não se pode a rmar nada sobre a decidibilidade de PC, porém PD é decidível. 
 
 10. Ref.: 6113910 Pontos: 1,00 / 1,00 
Considere os seguintes problemas de decisão: 
 
P1: Uma determinada máquina de estado nito aceita uma determinada cadeia. 
P2: Uma determinada gramática livre de contexto gera um número in nito de cadeias. 
Qual das seguintes a rmações é verdadeira? 
 Apenas P1 é decidível. 
 Apenas P2 é decidível. 
 Nem P1 nem P2 são decidíveis. 
 P1 e P2 não são problemas de decisão. 
 Ambos P1 e P2 são decidíveis.