av Automatos

Prévia do material em texto

1. Ref.: 6101909 Pontos: 0,00 / 1,00 
 
 
Palíndromos são cadeias que lidas da esquerda para a direita ou da direita para a esquerda têm a mesma 
sequência de símbolos e podem ser definidas pela seguinte expressão: wwR, onde w é uma cadeia e não há 
constante ou separador. Nesse contexto, assinale a alternativa em que todas as cadeias são palíndromos sem 
separador. 
 
 
 
 ANA, 1190911, 0010, ABA 
 00, 119911, 001100, AA 
 
001, 1199911, 0010, AABB 
 
001, 1190911, 0010, AABB 
 
010, 1190911, 00100, ANA 
 
 
 
 2. Ref.: 6101939 Pontos: 0,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 identificador 
válido dessa linguagem. 
 
Assinale a alternativa que tem uma derivação correta para a expressão 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). 
 
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). 
 
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>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). 
javascript:alert('Código%20da%20questão:%206101909.');
javascript:alert('Código%20da%20questão:%206101909.');
javascript:alert('Código%20da%20questão:%206101939.');
javascript:alert('Código%20da%20questão:%206101939.');
 
 
 
 3. Ref.: 6101772 Pontos: 0,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 
 00c1, 001c100, 00c10, c 
 
00c10, 11c11, 01c11, c 
 0c0, 11c11, 001c100, c 
 
0c0, 110c111, 001c100, c 
 
 
 
 
 
03492 - LINGUAGENS REGULARES 
 
 
 
 
 4. Ref.: 6096596 Pontos: 0,00 / 1,00 
 
 
Considere o seguinte Autômato Finito 
 
Sobre o autômato apresentado, assinale a afirmativa correta. 
 
 
 
 
A palavra vazia é reconhecida pelo autômato. 
 As palavras com número par de zeros e ímpar de uns são reconhecidas pelo autômato. 
 As palavras com número par de zeros e uns são reconhecidas pelo autômato. 
javascript:alert('Código%20da%20questão:%206101772.');
javascript:alert('Código%20da%20questão:%206101772.');
javascript:alert('Código%20da%20questão:%206096596.');
javascript:alert('Código%20da%20questão:%206096596.');
 
As palavras com número ímpar de zeros e par de uns são reconhecidas pelo autômato. 
 
As palavras com número ímpar de zeros e uns são reconhecidas pelo autômato. 
 
 
 
 5. Ref.: 6096597 Pontos: 1,00 / 1,00 
 
 
Considere o autômato finito mostrado na figura abaixo (os círculos concêntricos representam estado final) e 
assinale a afirmativa correta. 
 
 
 
 
 A palavra vazia é reconhecida pelo autômato. 
 
A palavra 10101 é reconhecida pelo autômato. 
 
A palavra vazia não é reconhecida pelo autômato. 
 
A palavra 101 é reconhecida pelo autômato. 
 
A palavra 01010 não é reconhecida pelo autômato. 
 
 
 
 6. Ref.: 6097036 Pontos: 1,00 / 1,00 
 
 
(POSCOMP / 2008) Seja o autômato finito mostrado na figura abaixo que opera sobre o alfabeto Σ = {a,b} (o 
círculo em negrito indica um estado terminal): 
 
javascript:alert('Código%20da%20questão:%206096597.');
javascript:alert('Código%20da%20questão:%206096597.');
javascript:alert('Código%20da%20questão:%206097036.');
javascript:alert('Código%20da%20questão:%206097036.');
Analise as seguintes afirmativas. 
I. O autômato finito mostrado na figura é determinístico. 
II. O autômato finito mostrado na figura é não-determinístico. 
III. O autômato finito mostrado na figura reconhece a palavra vazia 
A análise permite concluir que 
 
 
 
 
Somente as afirmativas I e II são falsas. 
 
Somente a afirmativa III é falsa. 
 
Somente a afirmativa II é falsa. 
 Somente a afirmativa I é falsa. 
 
Somente as afirmativas II e III são falsas. 
 
 
 
 
 
03493 - LINGUAGENS LIVRES DE CONTEXTO 
 
 
 
 
 7. Ref.: 6097352 Pontos: 1,00 / 1,00 
 
 
A linguagem gerada pelo GLC é chamada de linguagem livre de contexto (LLC). Acerca de suas características, 
a linguagem livre de contexto não é fechada em relação a: 
 
 
 
 
Divisão. 
 Complementação. 
 
Concatenação. 
 
Fechamento de Kleene. 
 
União. 
 
 
 
 8. Ref.: 6097521 Pontos: 1,00 / 1,00 
 
 
As gramáticas podem ser classificadas de acordo com o seu tipo. Na hierarquia de Chomsky a linguagem livre 
de contexto é a linguagem de: 
 
 
 
 
Tipo 3. 
javascript:alert('Código%20da%20questão:%206097352.');
javascript:alert('Código%20da%20questão:%206097352.');
javascript:alert('Código%20da%20questão:%206097521.');
javascript:alert('Código%20da%20questão:%206097521.');
 
Tipo 4. 
 Tipo 2. 
 
Tipo 1. 
 
Tipo 0. 
 
 
 
 
 
03494 - COMPUTABILIDADE E A MÁQUINA DE TURING 
 
 
 
 
 9. Ref.: 6113721 Pontos: 0,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. 
 PC é indecidível, contudo não se pode afirmar nada sobre a decidibilidade de PD. 
 
PC e PD são ambos indecidíveis. 
 
Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD. 
 
Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível. 
 
 
 
 10. Ref.: 6113910 Pontos: 0,00 / 1,00 
 
 
Considere os seguintes problemas de decisão: 
 
P1: Uma determinada máquina de estado finito aceita uma determinada cadeia. 
javascript:alert('Código%20da%20questão:%206113721.');
javascript:alert('Código%20da%20questão:%206113721.');
javascript:alert('Código%20da%20questão:%206113910.');
javascript:alert('Código%20da%20questão:%206113910.');
P2: Uma determinada gramática livre de contexto gera um número infinito de cadeias. 
 
Qual das seguintes afirmações é verdadeira? 
 
 
 
 
P1 e P2 não são problemas de decisão. 
 Ambos P1 e P2 são decidíveis. 
 
Apenas P1 é decidível. 
 
Nem P1 nem P2 são decidíveis. 
 Apenas P2 é decidível.