LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES_ CICLO I

Prévia do material em texto

18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/7
 
Meus Simulados
Teste seu conhecimento acumulado
Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES   
Aluno(a): LUCAS ADRIEL MARQUES DO NASCIMENTO 202009015344
Acertos: 9,0 de 10,0 17/04/2023
Acerto: 1,0  / 1,0
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual o tipo da seguinte gramática: S → aSb  e S → ab
Com estrutura de frase
Sensível ao Contexto
Regular
Irrestrito
 Livre de Contexto
Respondido em 17/04/2023 19:38:55
Explicação:
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção atendendo às seguintes restrições: 1. Todas as
regras de produção devem ser do tipo (Não-terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado atende a essas
duas restrições.
 Questão1
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/7
Acerto: 1,0  / 1,0
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual é o maior número de tipo para a gramática dada pelas seguintes regras de produção S → Aa, A → c | Ba, B → abc.
 Dois
Três
Um
Zero
Quatro
Respondido em 17/04/2023 19:39:05
Explicação:
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção atendendo às seguintes restrições: 1. Todas as
regras de produção devem ser do tipo (Não-terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado atende a essas
duas restrições.
Acerto: 1,0  / 1,0
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual o tipo da seguinte gramática?
 
S → aS/A
aS → aa
A → a
 Questão2
a
 Questão3
a
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/7
 Sensível ao Contexto
Regular
Com estrutura de frase
Irrestrito
Livre de Contexto
Respondido em 17/04/2023 19:40:04
Explicação:
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção atendendo às seguintes restrições: 1. Todas as
regras de produção devem ser do tipo (Não-terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado tem uma regra
que torna sensível ao contexto, ao ter um símbolo não-terminal do lado esquerdo da produção.
Acerto: 1,0  / 1,0
(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Gramática de pilha.
Gramática livre de contexto.
Gramática sensível ao contexto.
 Gramática regular.
Gramática irrestrita.
Respondido em 17/04/2023 19:46:33
Explicação:
Gabarito: Gramática regular.
Justi�cativa: A primeira fase do compilador chamada analisador léxico é projetada pelos autômatos �nitos, que são os reconhecedores
das expressões regulares geradas pelas gramáticas regulares.
Acerto: 1,0  / 1,0
 Questão4
a
 Questão
5
a
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/7
Com base nas a�rmativas abaixo assinale a resposta correta:
I.  As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos �nitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato �nito existe sempre um estado inicial �xo.
IV. Gramáticas têm um número �nito de regras de produção.
 I, III e IV, apenas
II e IV, apenas
I, II e IV, apenas
I e IV, apenas.
II e III, apenas
Respondido em 17/04/2023 20:33:34
Explicação:
Gabarito: I, III e IV, apenas
Justi�cativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
Acerto: 1,0  / 1,0
(POSCOMP / 2008) Considere o autômato �nito mostrado na �gura abaixo (os círculos em negrito representam estados
terminais)
A esse respeito, assinale a a�rmativa FALSA.
A palavra vazia é reconhecida pelo autômato.
 Questão6
a
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/7
A palavra ababa não é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.
 A palavra aba é reconhecida pelo autômato.
Respondido em 17/04/2023 20:03:35
Explicação:
Gabarito: A palavra aba é reconhecida pelo autômato.
Justi�cativa: Esse AFN realiza uma transição em ε para um estado �nal, logo reconhece a palavra vazia. Essa mesma transição permite
o reconhecimento de baba. Existe um caminho para o reconhecimento de aaa e ababa não é reconhecida. Logo, todas essas
alternativas são verdadeiras.  A palavra aba não é reconhecida pelo autômato porque não há caminhos que levem a um estado �nal.
Essa alternativa é falsa.
Acerto: 1,0  / 1,0
A Forma Normal de Chomsky é um outro tipo de forma normal, além da BNF. Qual das seguintes produções está em CNF (NT =
Não Terminal)?
(NT) → (Cadeia de exatamente três terminais)
(NT) → (Cadeia de exatamente quatro terminais)
(NT) → (Cadeia de um terminal e três não terminais)
 (NT) → (Cadeia de exatamente dois NT)
(NT) → (Cadeia de cinco ou mais NT)
Respondido em 17/04/2023 20:40:55
Explicação:
Gabarito: (NT) → (Cadeia de exatamente dois NT)
Justi�cativa: A forma normal CNF é aquela em que o número de símbolos à direita de uma produção é estritamente limitado. Em
particular, a cadeia à direita de uma produção consiste em não mais que dois símbolos.
 Questão7
a
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/7
Acerto: 0,0  / 1,0
Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de
produção dessa GLC, é denominada de:
 Irrestrita (sem restrições).
 Finita.
Sem contexto.
Recursiva.
In�nita.
Respondido em 17/04/2023 20:42:17
Explicação:
Gabarito: Finita.
Justi�cativa: Uma linguagem L gerada a partir de uma dada GLC é �nita se não houver ciclos no grafo direcionado gerado a partir das
regras de produção dessa GLC.
Acerto: 1,0  / 1,0
O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar,
para qualquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo
problema também pode ser assim descrito: dados um algoritmo e uma entrada �nita, decidir se o algoritmo termina ou se
executará inde�nidamente. Para o problema da parada:
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona,
fornecendo respostas aproximadas. 
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona,
fornecendo respostas aproximadas.
Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado. 
Respondido em 17/04/2023 20:12:51
 Questão8
a
 Questão9
a
18/04/2023, 09:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 7/7
Explicação:
Não existe nenhuma máquina de Turing M que consiga decidir se vai parar ou entrar em loop in�nito. O problema da parada é
indecidível, portanto não existe algoritmo que o solucione.
Acerto: 1,0  / 1,0
A hierarquia de Chomsky representou um marco na classi�cação das linguagens e uma grande evolução para a computação.
Acerca das características das diferentes linguagens e as respectivas máquinas reconhecedoras dessaslinguagens, Aassinale a
alternativa falsa.
O conjunto de todas as Máquinas de Turing é enumerável.
Toda Linguagem Regular é enumerável.
O conjunto de todas as Expressões Regulares é enumerável.
 Nenhum Conjunto Finito é enumerável.
Todo Conjunto Finito é enumerável.
Respondido em 17/04/2023 20:19:05
Explicação:
Os conjuntos enumeráveis são os superconjuntos de todas as linguagens tratáveis por autômatos (no caso a máquina de Turing).
Portanto, há linguagens in�nitas cujas gramáticas são uma especi�cação �nita e são enumeráreis e aceitas por Máquinas de Turing.
Outo contraexemplo é o conjunto dos números naturais.
 Questão10
a