Baixe o app para aproveitar ainda mais
Prévia do material em texto
16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 1/7 Teste de Conhecimento avalie sua aprendizagem 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 TEORIA DA COMPUTAÇÃO Lupa Calc. CCT0832_A7_202107065796_V1 Aluno: JUCELINO COSTA DE OLIVEIRA Matr.: 202107065796 Disc.: TEORIA DA COMPUTAÇÃO 2023.1 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. apenas as assertivas II e III. nenhuma das assertivas. javascript:voltar(); javascript:voltar(); javascript:diminui(); javascript:aumenta(); javascript:calculadora_on(); 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 2/7 Analise as seguintes a�rmativas. I. Todo autômato �nito não-determinístico pode ser simulado por um autômato �nito determinístico. II. Todo autômato �nito determinístico pode ser simulado por um autômato �nito não-determinístico. III. Todo autômato �nito 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 �nito não-determinístico. V. Todo autômato �nito não-determinístico pode ser simulado por uma máquina de Turing determinística. A análise permite concluir que estão CORRETAS apenas as assertivas I e III. todas as assertivas. apenas as assertivas I e II. Explicação: (A) apenas as assertivas I e II. (B) apenas as assertivas I e III. (C) apenas as assertivas II e III. (D) todas as assertivas. (E) nenhuma das assertivas. Resolução As a�rmativas 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 a�rmativa 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. 2. 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 3/7 Analise as seguintes a�rmativas.I. Todo autômato �nito não-determinístico pode ser simulado por um autômato �nito determinístico. II. Todo autômato �nito determinístico pode ser simulado por um autômato �nito não-determinístico. III. Todo autômato �nito 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 �nito não-determinístico. V. Todo autômato �nito não-determinístico pode ser simulado por uma máquina de Turing determinística. A análise permite concluir que estão CORRETAS apenas as a�rmativas I, II, III e IV. apenas as a�rmativas II, III e V. apenas as a�rmativas I, II, III e V. apenas as a�rmativas I, II e IV. apenas as a�rmativas II e IV. Explicação: (A) apenas as a�rmativas I, II, III e IV. (B) apenas as a�rmativas II, III e V. (C) apenas as a�rmativas I, II, III e V. (D) apenas as a�rmativas II e IV. (E) apenas as a�rmativas I, II e IV. Resolução A única a�rmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos �nitos reconhecem linguagens regulares. Portanto, é impossível simular um autômato de pilha utilizando um autômato �nito, pois a classe de linguagens que esse último reconhece é hierarquicamente inferior. Além disso, autômatos �nitos não possuem memória auxiliar para simular a pilha. Logo, a alternativa correta é a C. 3. apenas as a�rmativas II e IV. 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 4/7 Para gerar o automâto �nito mínimo a partir um automâto �nito o devemos pelo algoritmo de minimização é necessario que: apenas as a�rmativas II, III e V. apenas as a�rmativas I, II, III e IV. apenas as a�rmativas I, II, III e V. apenas as a�rmativas I, II e IV. Explicação: (A) apenas as a�rmativas I, II, III e IV. (B) apenas as a�rmativas II, III e V. (C) apenas as a�rmativas I, II, III e V. (D) apenas as a�rmativas II e IV. (E) apenas as a�rmativas I, II e IV. Resolução A única a�rmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos �nitos reconhecem linguagens regulares. Portanto, é impossível simular um autômato de pilha utilizando um autômato �nito, pois a classe de linguagens que esse último reconhece é hierarquicamente inferior. Além disso, autômatos �nitos não possuem memória auxiliar para simular a pilha. Logo, a alternativa correta é a C. 4. A função programa seja parcial Ele seja deterministico Todos os estados sejam alcançaveis a partir de qualquer outro estado A partir de uma estado existam 0, 1 ou n transições Ele tenha destinos inalcançaveis Explicação: Algoritmo de Minimização de Autômatos PRE-REQUISITOS DO AUTÔMATO A SER MINIMIZADO 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 5/7 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? Sobre a hierarquia de Chomsky podemos a�rmar que: 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 5. {a,b,f} {a,b,f,c,g,h,i} {a,c,g,h,i} {a,b,f,c,g} {a,c,g} 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. 6. 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 6/7 Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular Uma linguagem que não é regular é livre de contexto As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem As linguagens reconhecidas por autômatos a pilha são as linguagens regulares Há linguagens que não são nem livres de contexto nem sensíveis ao contexto 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 aocontexto 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 a�rmaçã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). 16/04/2023, 13:32 Estácio: Alunos https://simulado.estacio.br/alunos/ 7/7 Não Respondida Não Gravada Gravada Exercício inciado em 16/04/2023 13:30:31. javascript:abre_colabore('35479','306275308','6186067933');
Compartilhar