TEORIA DA COMPUTAÇÃO-TESTE DE CONHECIMENTO-07

Prévia do material em texto

11/3/21, 9:41 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 1/4
Teste de
Conhecimento
 avalie sua aprendizagem
Para gerar o automâto finito mínimo  a partir um automâto finito o devemos  pelo algoritmo de minimização é necessario que:
Seja a seguinte linguagem, onde ϵ representa a sentença vazia
SABCD→AB|CD→a|ϵ→b|f→c|g→h|i
Qual o conjunto de terminais que podem começar sentenças derivadas de S?
TEORIA DA COMPUTAÇÃO
Lupa   Calc.
   
   
CCT0832_A7_202004135813_V1 
 
Aluno: ALESSANDRO VIANA DE ARAUJO Matr.: 202004135813
Disc.: TEORIA DA COMPUTAÇÃO  2021.3 EAD (G) / EX
 
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O
mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se familiarizar com este
modelo de questões que será usado na sua AV e AVS.
 
1.
Ele tenha destinos inalcançaveis
Ele seja  deterministico
A partir de uma estado existam  0, 1 ou n transições
 
Todos os estados sejam  alcançaveis a partir de qualquer outro estado
A função programa seja parcial
 
 
 
Explicação:
Algoritmo de Minimização de Autômatos
PRE-REQUISITOS DO AUTÔMATO A SER MINIMIZADO
a.Deve ser determinístico
b.Todos os estados devem poder ser alcançados a partir do estado inicial (Sem estados inalcançáveis
c.A função programa deve ser total, ou seja, a partir de qualquer estado deve haver transições para todos os símbolos do alfabeto
 
 
 
 
2.
{a,b,f,c,g}
 
{a,c,g,h,i}
 
{a,c,g}
{a,b,f}
{a,b,f,c,g,h,i}
 
 
 
 
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
11/3/21, 9:41 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 2/4
Sobre a hierarquia de Chomsky podemos afirmar que: 
Analise as seguintes afirmativas.I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.
II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
III. Todo autômato finito não-determinístico pode ser simulado por um autômato de pilha determinístico.
IV. Todo autômato de pilha determinístico pode ser simulado por um autômato finito não-determinístico.
V. Todo autômato finito não-determinístico pode ser simulado por uma máquina de Turing determinística.
A análise permite concluir que estão CORRETAS
Explicação:
(A) {a,c,g}
(B) {a,b,f,c,g}
(C) {a,b,f,c,g,h,i}
(D) {a,c,g,h,i}
(E) {a,b,f}
Resolução
Na prática, o enunciado solicita o conjunto FIRST de S.
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e C fazem parte do conjunto: {a,c,g}. Como A produz a cadeia
vazia, então devemos também incluir os não terminais que iniciam sentenças produzidas pelo não terminal B: {b,f}.
Unindo os conjuntos, temos: {a,b,c,f,g}. Portanto, a alternativa correta é a B.
 
 
 
 
3.
 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
 
 Uma linguagem que não é regular é livre de contexto
 
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
 
 
 
 
 
Explicação:
a - Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
b-  As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
c -  Uma linguagem que não é regular é livre de contexto
d - As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
e -  Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
A alternativa A é falsa. Segue o teorema das linguagens recursivamente enumeráveis:
Teorema: Qualquer linguagem gerada por uma gramática irrestrita é recursivamente enumerável .
Uma das consequências desse teorema é que todas as linguagens regulares são recursivamente enumeráveis, uma vez que toda gramática
regular também é irrestrita.
Toda linguagem livre de contexto também é sensível ao contexto, portanto a alternativa B é falsa.
A alternativa C está errada porque quando uma linguagem não é regular, ela também pode ser sensível ao contexto ou irrestrita.
A alternativa D está errada. As linguagens reconhecidas por autômatos a pilha são linguagens livres de contexto. Apesar das linguagens
regulares também serem livres de contexto e, portanto, também serem reconhecidas por um autômato a pilha, a afirmação exclui as linguagens
que são puramente livres de contexto.
A alternativa E está correta. Tais linguagens são irrestritas (ou estruturadas em frase).
 
 
 
 
4.
apenas as afirmativas II, III e V.
apenas as afirmativas II e IV.
apenas as afirmativas I, II, III e IV.
apenas as afirmativas I, II e IV.
 apenas as afirmativas I, II, III e V.
 
 
 
 
Explicação:
11/3/21, 9:41 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 3/4
Analise as seguintes afirmativas.
I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.
II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
III. Todo autômato finito não-determinístico pode ser simulado por um autômato de pilha determinístico.
IV. Todo autômato de pilha determinístico pode ser simulado por um autômato finito não-determinístico.
V. Todo autômato finito não-determinístico pode ser simulado por uma máquina de Turing determinística.
A análise permite concluir que estão CORRETAS
Seja a linguagem formal L={anb2nc,n≥0}. Analise as seguintes assertivas.
I. L é uma linguagem livre de contexto.
II. A gramática G=({S,X},{a,b,c},{S→Xc,X→aXbb|ϵ},S) gera a linguagem L.
III. L não pode ser reconhecida por um autômato com pilha.
A análise permite concluir que estão CORRETAS
 
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos finitos reconhecem
linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens que esse último reconhece é
hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
 
 
 
 
5.
apenas as afirmativas I, II e IV.
apenas as afirmativas II e IV.
 
apenas as afirmativas II, III e V.
 
apenas as afirmativas I, II, III e V.
 
apenas as afirmativas I, II, III e IV.
 
 
 
 
Explicação:
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos finitos reconhecem
linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens que esse último reconhece é
hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
 
 
 
 
6.
apenas as assertivas I e II.
 
nenhuma das assertivas.
todas as assertivas.
 
apenas as assertivas II e III.
 
apenas as assertivas I e III.
 
 
 
Explicação:
(A) apenas as assertivas I e II.
(B) apenas as assertivas I e III.
11/3/21, 9:41 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 4/4
(C) apenas as assertivas IIe III.
(D) todas as assertivas.
(E) nenhuma das assertivas.
Resolução
As afirmativas I e II estão corretas. A gramática G é livre de contexto e produz corretamente a linguagem L.
A produção X→aXbb|ϵ produz anb2n, isto é, para cada a à esquerda, teremos dois b's à direita. Essa "simetria" não pode ser expressa por uma
gramática regular.
Uma vez que a gramática G é livre de contexto, então a linguagem L, produzida por G, é livre de contexto.
A afirmativa III está incorreta, pois como a linguagem L é livre de contexto, então ela é reconhecida por um autômato com pilha.
Portanto, a alternativa correta é a A.
 
 
 
 
 
 
 
    Não Respondida      Não Gravada     Gravada
 
 
Exercício inciado em 03/11/2021 21:38:16. 
 
 
 
 
javascript:abre_colabore('34918','271367734','4962010928');