Baixe o app para aproveitar ainda mais
Prévia do material em texto
Disciplina: LLIINNGGUUAAGGEENNSS FFOORRMMAAIISS EE AAUUTTÔÔMMAATTOOSS AAVV Aluno: AALLAANNAA DDEE CCAARRVVAALLHHOO MMAARRIINNSS 220022331100331188664444 Professor: GGAABBRRIIEELL RREECCHH BBAAUU Turma: 99000011 DGT1397_AV_202310318644 (AG) 23/02/2024 14:00:31 (F) Avaliação: 33,,0000 pts Nota SIA: 33,,0000 pts Estação de trabalho liberada pelo CPF 10861514700 com o token 742373 em 23/02/2024 13:58:33. 0033449911 -- CCOONNCCEEIITTOOSS BBÁÁSSIICCOOSS DDEE AAUUTTÔÔMMAATTOOSS EE LLIINNGGUUAAGGEENNSS 11.. Ref.: 6101939 Pontos: 00,,0000 / 11,,0000 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): 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). 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). T =>3 T * F =>5 T * (E) =>1 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). 22.. Ref.: 6101772 Pontos: 00,,0000 / 11,,0000 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. 0c0, 110c111, 001c100, c 00c10, 11c11, 01c11, c 00c1, 001c100, 00c10, c 00c00, 1100011, 00100, c 0c0, 11c11, 001c100, c EPS https://simulado.estacio.br/bdq_prova_resultado_aluno_n.asp?cod_hist... 1 of 5 11/03/2024, 09:09 javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.'); 0033449922 -- LLIINNGGUUAAGGEENNSS RREEGGUULLAARREESS 33.. Ref.: 6097098 Pontos: 11,,0000 / 11,,0000 A teoria dos autômatos é o estudo de máquinas _______________ e os problemas computacionais relacionados a essas máquinas, chamadas de _______________. São aplicados em diferentes áreas da ciência da computação e da _______________. Sua aplicação mais tradicional é encontrada na construção de _______________. Assinale a alternativa que preenche, correta e respectivamente, as lacunas do trecho acima. abstratas - compiladores - engenharia - computadores automáticas - compiladores - engenharia - corretores ortográ�cos determinísticas - computadores - matemática - circuitos elétricos de estado �nito - computadores - TI - computadores abstratas - autômatos - engenharia - compiladores 44.. Ref.: 6096596 Pontos: 00,,0000 / 11,,0000 Considere o seguinte Autômato Finito Sobre o autômato apresentado, assinale a a�rmativa correta. As palavras com número ímpar de zeros e par de uns são reconhecidas pelo autômato. 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. As palavras com número ímpar de zeros e uns são reconhecidas pelo autômato. 55.. Ref.: 6097036 Pontos: 00,,0000 / 11,,0000 (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): EPS https://simulado.estacio.br/bdq_prova_resultado_aluno_n.asp?cod_hist... 2 of 5 11/03/2024, 09:09 javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.'); 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 II e III são falsas. Somente a a�rmativa II é falsa. Somente a a�rmativa I é falsa. Somente as a�rmativas I e II são falsas. Somente a a�rmativa III é falsa. 0033449933 -- LLIINNGGUUAAGGEENNSS LLIIVVRREESS DDEE CCOONNTTEEXXTTOO 66.. Ref.: 6097522 Pontos: 11,,0000 / 11,,0000 (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 aaaca ccca ccac aa 77.. Ref.: 6097350 Pontos: 00,,0000 / 11,,0000 EPS https://simulado.estacio.br/bdq_prova_resultado_aluno_n.asp?cod_hist... 3 of 5 11/03/2024, 09:09 javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.'); (ENADE / 2011) Considere a gramática a seguir em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a cadeia vazia. S → 1S | 0A | ε A → 1S | 0B | ε B → 1S | ε A respeito dessa gramática, analise as a�rmações a seguir. I. Nas cadeias geradas por essa gramática, o último símbolo é sempre 1. II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois. III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros. IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros. É correto apenas o que se a�rma em: III e IV I e III II I II e IV 0033449944 -- CCOOMMPPUUTTAABBIILLIIDDAADDEE EE AA MMÁÁQQUUIINNAA DDEE TTUURRIINNGG 88.. Ref.: 6113811 Pontos: 00,,0000 / 11,,0000 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(G11) ∩ L(G22) = ∅, é indecidível. Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina de Turing. 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. É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par. 99.. Ref.: 6113714 Pontos: 11,,0000 / 11,,0000 Embora uma máquina de Turing seja uma estrutura muito simples, ela é extremamente poderosa. Acerca de suas características, uma linguagem L é chamada aceitável, se existe uma máquina de Turing M que: I) Entra em loop in�nito para cadeias em L. II) Aceita L. EPS https://simulado.estacio.br/bdq_prova_resultado_aluno_n.asp?cod_hist... 4 of 5 11/03/2024, 09:09 javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.'); III) Rejeita L. IV) Resolve o problema em um tempo de execução polinomial. V) Resolve o problema da Parada. I, II e III. III, IV e V. I, III e V. II e III. IV e V. 1100.. Ref.: 6113910 Pontos: 00,,0000 / 11,,0000 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 P2 é decidível. P1 e P2 não são problemas de decisão. Apenas P1 é decidível. Ambos P1 e P2 são decidíveis. Nem P1 nem P2 são decidíveis. EPS https://simulado.estacio.br/bdq_prova_resultado_aluno_n.asp?cod_hist... 5 of 5 11/03/2024, 09:09 javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.'); javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.');
Compartilhar