Avaliação - Autômatos - Poscomp

Prévia do material em texto

FACULDADE UNINASSAU 
C CURSO DE GRADUAÇÃO EM ENGENHARIA ELÉTRICA 
 DISCIPLINA AUTOMAÇÃO INDUSTRIAL 
 
 2ª avaliação 
 
ALUNO MATRÍCULA 
DISCIPLINA DATA DA PROVA 
PROFESSOR TIPO DE PROVA 
TURMA 
CÓDIGO DA 
TURMA NOTA 
 
QUESTÕES: 
 
 
QUESTÃO 01: 
Seja a seguinte linguagem, onde ϵ representa a sentença vazia 
S → AB | CD 
A → a | ϵ 
B→b | f 
C →c | g 
D →h | i 
 
Qual o conjunto de terminais que podem começar sentenças derivadas de S? 
(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} 
 
QUESTÃO 02: 
Acerca das linguagens formais e dos autômatos, assinale a opção correta. 
 INSTRUÇÕES - LEIA COM ATENÇÃO 
 
• Esta avaliação tem valor de 8,0 (oito) pontos; 
• Esta avaliação conta com 10 questões objetivas; 
• Cada questão contém uma única resposta correta; 
• Todas as questões devem conter as suas respectivas justificativas; 
• Questões sem justificativas serão desconsideradas; 
• Justificativas copiadas da internet ou idênticas à de qualquer outro aluno resultará na 
anulação da questão; 
• A avaliação deverá ser entregue em 03 de novembro de 2020, até às 23h; 
• Você pode utilizar este arquivo para colocar as suas respostas: marque a resposta 
correta com marca texto (exemplo), bem como as justificativas para cada questão. 
• Se preferir fazer as justificativas escritas manualmente, entregue todas as 
respostas em um ÚNICO arquivo em PDF. 
• Esta avaliação deverá ser entregue na plataforma (teams) como anexo da tarefa 
atribuída. 
 
Sucesso! 
 
 
darla
Realce
 FACULDADE UNINASSAU 
C CURSO DE GRADUAÇÃO EM ENGENHARIA ELÉTRICA 
 DISCIPLINA AUTOMAÇÃO INDUSTRIAL 
 
 2ª avaliação 
 
a) A máquina de Turing capaz de simular outras máquinas de Turing é uma 
Turing completa, chamada máquina de Turing universal, capaz de calcular 
qualquer função recursiva, decidir qualquer linguagem recursiva e aceitar 
qualquer linguagem enumeravelmente recursiva. 
b) Os autômatos finitos consistem na idealização de um computador capaz de 
acessar uma quantidade limitada de processos, o que restringe o 
processamento de informações de forma paralela; portanto, computadores 
desse gênero têm sua utilização limitada a aplicações simples, como, por 
exemplo, controlar elevadores ou portas automáticas. 
c) Nos autômatos de pilha, existe uma estrutura de controle, que representa 
os estados e as funções de transição, e um input, que o autômato lê da 
esquerda para a direita, uma casa de cada vez, atualizando a estrutura de 
controle. 
d) Os autômatos de pilha são modelos com uma quantidade de memória finita. 
Por sua vez, um autômato finito, apesar da limitada capacidade de 
processamento, por meio de uma pilha, consegue acessar a uma 
quantidade infinita de memória. 
e) Os autômatos de pilha correspondem a um modelo mais poderoso que as 
máquinas de Turing, visto que permitem fazer várias operações pop sem 
perder informações. 
 
QUESTÃO 03: 
Qual das seguintes afirmações é falsa? 
(A) Dada uma máquina de Turing M com alfabeto de entrada Σ e 
uma string w∈Σ, não se sabe se a computação de M com entrada w vai ou não 
parar. 
(B) O problema da parada é indecidível. 
(C) Não existe algoritmo que determina quando uma gramática livre de 
contexto arbitrária é ambígua. 
(D) Não existe autômato finito determinístico que reconheça alguma linguagem 
livre de contexto. 
(E) Um autômato com duas pilhas pode ser simulado por uma máquina de 
Turing. 
 
QUESTÃO 04: 
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→X|c, 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 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. 
darla
Realce
darla
Realce
darla
Realce
 FACULDADE UNINASSAU 
C CURSO DE GRADUAÇÃO EM ENGENHARIA ELÉTRICA 
 DISCIPLINA AUTOMAÇÃO INDUSTRIAL 
 
 2ª avaliação 
 
 
QUESTÃO 05: 
A gramática G = ({S, A, B}, {0, 1}, P, S), onde P é dado pelas regras de 
produção 
S → 0AB | 1BA 
A → 0AS | 1A | ε 
B → 0B | 1BS | ε 
gera uma linguagem que 
(A) pertence à classe Regular. 
(B) contém a cadeia vazia ε. 
(C) pode ser aceita por um autômato com pilha. 
(D) pode ser denotada por uma expressão regular. 
(E) é igual ao conjunto de cadeias { x ∈ {0, 1}* | x tem quantidade igual de zero 
(0) e de um (1) } 
 
QUESTÃO 06: 
Sobre as linguagens regulares, considere as afirmativas a seguir. 
I. As linguagens regulares podem ser expressas por máquinas de Moore e 
de Mealy. 
II. As linguagens regulares podem ser expressas por um autômato finito. 
 III. Se A e B são linguagens regulares, então A ∩ B também é. 
IV. Seja B = {ba, na}. Pode-se dizer que B∗ = {λ, ba, na, ab, an, 
baba, bana, naba, anab, nana, aban, bababa, babana, banaba, banana, 
nababa, nabana, nanaba, nanana, abanba, babababa, ...}. 
Assinale a alternativa correta. 
a) Somente as afirmativas I e II são corretas. 
b) Somente as afirmativas I e IV são corretas. 
c) Somente as afirmativas III e IV são corretas. 
d) Somente as afirmativas I, II e III são corretas. 
e) Somente as afirmativas II, III e IV são corretas. 
 
QUESTÃO 07: 
Assinale a alternativa que apresenta, corretamente, uma expressão regular que 
denota todas as strings de a’s e b’s que têm pelo menos 
dois b’s consecutivos. 
a) (a*+bb)(a+ba)*(a+b)* 
b) (a+ba)*bb(ba+a)* 
c) (a+b)*ba*b(a+b)* 
d) (a+bb)*(bb+a)* 
e) (a+ba)*bb(a+b)* 
 
QUESTÃO 08: 
Analise as seguintes igualdades de expressões regulares: 
I. a∗=(a∗)∗ 
II. (a+b)∗=(b+a)∗ 
III. a∗+b∗=(a+b)∗ 
A análise permite concluir que 
darla
Realce
darla
Realce
darla
Realce
 FACULDADE UNINASSAU 
C CURSO DE GRADUAÇÃO EM ENGENHARIA ELÉTRICA 
 DISCIPLINA AUTOMAÇÃO INDUSTRIAL 
 
 2ª avaliação 
 
(A) somente as igualdades I e II são verdadeiras. 
(B) somente a igualdade I é verdadeira. 
(C) somente as igualdades II e III são verdadeiras. 
(D) todas as igualdades são verdadeiras. 
(E) nenhuma das igualdades é verdadeira. 
 
QUESTÃO 09: 
Qual é a linguagem da gramática com as seguintes regras de produção 
S→ASb | c 
A→a 
(A) {ancb | n∈N} 
(B) {acbn | n∈N} 
(C) {ancnb | n∈N} 
(D) {ancbn| n∈N} 
(E) Nenhuma das respostas 
 
QUESTÃO 10: 
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 
(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. 
 
 
 
 
 
darla
Realce
darla
Realce
darla
Realce
 
Questão 1 
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e 
C fazem parte do conjunto: {a,c,g}{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}{b,f}. 
Unindo os conjuntos, temos: {a,b,c,f,g}{a,b,c,f,g}. Portanto, a alternativa 
correta é a B. 
Fonte: https://www.blogcyberini.com/2017/11/poscomp-linguagens-formais-automatos-02.html 
Questão 2 
O filme O jogo da Imitação, relata a história de Alan Turing e a teoria da sua 
máquina, a máquina foi construída com o intuito de ser uma máquina universal 
capaz de decifrar qualquer criptografia. Á máquina possui uma fita que pode 
ser infinita tanto pra direita como para a esquerda, um cabeçote que pode ler e 
escrever símbolos na fita e também pode se move tanto para um lado como 
para outro. Um registrador de estados e uma tabela com as funções de 
transição. 
Questão 3 
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por 
autômatos finitos determinístico e, pela hierarquia de Chomsky, toda linguagem 
regular também é livre de contexto. 
Fonte:https://www.blogcyberini.com/2017/11/poscomp-linguagens-formais-
automatos-02.html 
Questão 4 
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|ϵX→aXbb|ϵ produz anb2nanb2n, 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. 
A alternativa correta é a A. 
Fonte: https://www.blogcyberini.com/2017/11/poscomp-linguagens-formais-
automatos-02.html 
Questão 5 
Toda linguagem livre de contexto pode ser entendida por um autômato com 
pilha, e g é uma gramática livre de contexto. Sabemos que gramaticas livres de 
contextos geram linguagens livres de contexto, assim sendo a resposta correta 
é a letra C. 
Resposta baseada no site : https://www.blogcyberini.com/2018/03/poscomp-
linguagens-formais-automatos-04.html 
Questão 6 
Utilizando os autômatos finitos, podemos expressar as linguagens regulares 
tanto na máquina de Moore quanto pela máquina de Mealy. Por tanto, temos 
como alternativas corretas, apenas as I, II e III. 
Questão 7 
Nesta questão eu tentei fazer no Jflap, mas não sei se está correta 
O resultado não saiu igual, mas saiu parecido com a questão 
(E). Questão 8 
A afirmativa I está correta. 
A afirmativa II também está correta. 
A afirmativa III está errada. Enquanto a expressão regular à esquerda 
reconhece cadeias contendo apenas a's ou cadeias contendo apenas b's, a 
expressão regular à direita reconhece qualquer cadeia de a's e b's. Por 
exemplo, a cadeia aab é reconhecida por (a|b)∗(a|b)∗, mas não é reconhecida 
por a∗|b∗. 
Fonte: https://www.blogcyberini.com/2017/11/poscomp-linguagens-formais-
automatos-02.html 
Questão 9 
Podemos simplificar a gramática por S -> aSb|c e A -> a, assim qualquer (b) 
gerado a esquerda terá um (a) na direita e consequentemente um (c) no meio. 
Resposta correta letra D 
Questão 10 
É impossível simular um autômato de pilha utilizando um autômato finito, pois a 
classe de linguagens que esse último reconhece é hierarquicamente inferior. 
autômatos finitos não possuem memória auxiliar para simular a pilha. 
Fonte: https://www.blogcyberini.com/2017/11/poscomp-linguagens-formais-
automatos-02.html 
	AVALIAÇÃO LFA UNIDADE II.pdf
	Questão 1