Linguagens Formais e Automatos_Questionario 2

Prévia do material em texto

• Pergunta 1 
• Pergunta 1 
0,5 em 0,5 pontos 
 
Complete as lacunas na afirmação a seguir: 
 
"As expressões regulares não conseguem representar completamente as 
Linguagens Livres de Contexto devido à ocorrência de ______(I)_______ na 
construção das cadeias destas; assim, para representar as regras de 
substituição destas gramáticas utiliza-se ________(II)_________." 
 
Resposta 
Selecionada: 
a. 
I: Encadeamentos; II: o Formalismo de Backus-
Naur. 
Respostas: a. 
I: Encadeamentos; II: o Formalismo de Backus-
Naur. 
 b. 
I: Encadeamentos; II: a Máquina de Turing. 
 c. 
I: Fechos de Kleene; II: a Máquina de Turing. 
 
d. 
I: Fechos de Kleene; II: o Formalismo de Backus-
Naur. 
 e. 
I: Encadeamentos; II: Autômatos Finitos. 
Comentário 
da resposta: 
Resposta: A 
Comentário: a representação das Linguagens do Tipo 2 
na Hierarquia de Chomsky precisa de outra forma de 
representação. O Formalismo de Backus-Naur não tem a 
força matemática das Expressões Regulares, mas 
permite representar uma gramática de uma forma mais 
sucinta do que as formas usuais. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Analise as afirmações acerca do Formalismo de Backus-Naur: 
 
I. Só pode ser utilizado para gramáticas livres de contexto 
II. Diferente das expressões regulares, não se baseia em operações, 
sendo apenas uma forma mais simplificada de representar uma 
gramática. 
III. Gramáticas representadas nesta forma não podem ser 
representadas na forma de um autômato. 
 
 
Estão corretas: 
Resposta Selecionada: b. 
A afirmação II apenas. 
Respostas: a. 
As afirmações I e III. 
 b. 
A afirmação II apenas. 
 c. 
A afirmação III apenas. 
 d. 
As afirmações II e III. 
 e. 
Todas as afirmações. 
Comentário 
da resposta: 
Resposta: B 
Comentário: a forma de Backus-Naur pode ser utilizada 
tanto para gramáticas livres de contexto quanto para 
gramáticas regulares. Estas gramáticas podem ser 
representadas por autômatos, finitos ou de pilha, 
dependendo das características da linguagem. 
 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
Em relação à memória auxiliar em um Autômato (finito ou de pilha), 
assinale a alternativa correta: 
 
Resposta 
Selecionada: 
e. 
Pode não ser necessária em um autômato finito, 
dependendo da gramática correspondente. 
Respostas: a. 
Sempre assumirá a forma de uma pilha como estrutura 
de dados, para qualquer autômato. 
 
b. 
Se assumir a forma de uma pilha, o autômato só 
poderá ser empregado exclusivamente para 
Linguagens do Tipo 2 (Linguagens Livres de Contexto). 
 
c. 
Seu uso só é necessário pra Linguagens do Tipo 1 
(Linguagens sensíveis ao contexto). 
 
d. 
Qualquer tipo de autômato sempre necessitará de uma 
memória auxiliar, independente da forma desta. 
 
 
e. 
Pode não ser necessária em um autômato finito, 
dependendo da gramática correspondente. 
Comentário da 
resposta: 
Resposta: E 
Comentário: autômatos finitos, determinísticos ou não, 
não precisam de uma memória auxiliar; porém, está é 
necessária na construção dos autômatos de pilha, na 
forma da própria pilha. 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
Considere a Hierarquia de Chomsky como apresentada na imagem. Um Autômato de Pilha 
pode ser utilizado como reconhecedor para uma gramática: 
 
 
Resposta Selecionada: e. 
Dos tipos 2 e 3. 
Respostas: a. 
Dos tipos 1, 2 e 3. 
 b. 
Do tipo 1, apenas. 
 c. 
Do tipo 2, apenas. 
 d. 
Do tipo 3, apenas. 
 e. 
Dos tipos 2 e 3. 
Comentário da 
resposta: 
Resposta: E 
Comentário: autômatos de pilha podem ser utilizados como 
reconhecedores tanto para Linguagens Livres de Contexto quanto para 
Linguagens Regulares. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
Uma Linguagem Irrestrita apresenta como característica das regras 
de substituição da sua gramática: 
 
Resposta 
Selecionada: 
d. 
Qualquer substituição é possível desde que do lado 
esquerdo exista pelo menos um símbolo não terminal e 
também que o lado direito possua uma quantidade de 
símbolos não inferior àquela encontrada no lado 
esquerdo da mesma regra. 
Respostas: a. 
 
Um símbolo terminal só pode ser substituído por um 
par de símbolos, sendo um deles terminal e outro não 
terminal (em qualquer ordem). 
 
b. 
Um símbolo terminal só pode ser substituído por um 
aninhamento contendo um símbolo terminal, um não 
terminal e outro terminal, nesta ordem. 
 
c. 
Qualquer substituição é possível desde que do lado 
esquerdo da regra haja ao menos um símbolo não 
terminal. 
 
d. 
Qualquer substituição é possível desde que do lado 
esquerdo exista pelo menos um símbolo não terminal e 
também que o lado direito possua uma quantidade de 
símbolos não inferior àquela encontrada no lado 
esquerdo da mesma regra. 
 
e. 
Qualquer substituição é possível desde que sem 
nenhum tipo de restrição (daí o nome irrestrita). 
Comentário 
da resposta: 
Resposta: D 
Comentário: as gramáticas irrestritas, apesar do nome, 
não aceitam quaisquer regras de substituição: os 
símbolos que estão substituídos devem conter ao 
menos um símbolo não terminal, e a substituição deve 
ser feita por uma quantidade maior ou igual de símbolos 
(não pode haver diminuição do número de símbolos na 
cadeia que está sendo formada). 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Indique a alternativa incorreta sobre Máquinas de Turing. 
Resposta 
Selecionada: 
c. 
É uma estrutura necessariamente não determinística. 
Respostas: a. 
A fita de entrada é sempre infinita à direita, podendo, 
em alguns casos, também ser infinita à esquerda. 
 
b. 
O cursor pode avançar e retroceder na fita, conforme 
o valor lido. 
 c. 
 
É uma estrutura necessariamente não determinística. 
 
d. 
O cursor pode gravar na fita de entrada, alterando seu 
conteúdo. 
 
e. 
É uma forma de representar um algoritmo 
computacional. 
Comentário da 
resposta: 
Resposta: C 
Comentário: Máquinas de Turing, como avançam ou 
retrocedem de acordo com valor lido na fita, não 
podem ser não determinísticas. 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
Indique a alternativa correta sobre Autômatos Finitos não 
Determinísticos. 
 
Resposta 
Selecionada: 
c. 
Uma transição pode ser feita de um estado para vários 
estados distintos. 
Respostas: a. 
É equivalente ao Autômato Finito Determinístico, 
porém com uma pilha associada. 
 
b. 
É uma forma mais elaborada dos Autômatos Finitos 
Determinísticos, possuindo sempre maior quantidade 
de estados e regras de transição. 
 
c. 
Uma transição pode ser feita de um estado para vários 
estados distintos. 
 
d. 
Sendo não determinísticos, suas transições são 
baseadas em probabilidades. 
 
e. 
Este tipo de autômato não é aplicável para o 
reconhecimento de Linguagens Regulares. 
Comentário da 
resposta: 
Resposta: C 
Comentário: as funções de transição deste tipo de 
autômato não contêm apenas um único estado 
“seguinte”, podendo conter um conjunto de próximos 
estados. 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
As Gramáticas Livres de Contexto apresentam o conceito de 
aninhamento nas suas regras de substituição. Isto significa que: 
 
Resposta 
Selecionada: 
a. 
Um símbolo não terminal é substituído por um 
símbolo terminal, um não terminal e outro terminal, 
nesta ordem. 
Respostas: a. 
Um símbolo não terminal é substituído por um 
símbolo terminal, um não terminal e outro terminal, 
nesta ordem. 
 
b. 
Um símbolo não terminal é substituído por um par de 
símbolos terminais. 
 
c. 
Um símbolo terminal é substituído por um par de 
símbolos, sendo um terminal e outro não terminal, 
nesta ordem. 
 
d. 
Um símbolo terminal é substituído por um par de 
símbolos, sendo um não terminal e outro terminal, 
nesta ordem. 
 
e. 
Um símbolo não terminal é substituído por um par de 
símbolos não terminais. 
Comentário da 
resposta: 
Resposta: A 
Comentário: uma regra de substituição quecontenha 
um aninhamento irá substituir um símbolo não 
terminal por um símbolo terminal, um não terminal e 
outro terminal, nesta ordem. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
Uma Máquina de Turing com fita limitada à esquerda irá reconhecer 
Linguagens: 
 
Resposta 
Selecionada: 
b. 
Dependentes do Contexto, Livres de Contexto e 
Regulares. 
Respostas: a. 
Dependentes do Contexto, Livres de Contexto e 
Irrestritas. 
 
 
b. 
Dependentes do Contexto, Livres de Contexto e 
Regulares. 
 c. 
Livres de Contexto e Regulares. 
 d. 
Livres de Contexto e Irrestritas. 
 e. 
De qualquer tipo. 
Comentário da 
resposta: 
Resposta: B 
Comentário: Máquinas de Turing com fita limitada 
reconhecem as Dependentes do Contexto (Tipo 1), 
Livres de Contexto (Tipo 2) e Regulares (Tipo 3). 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Analise as afirmações acerca dos Autômatos de Pilha: 
 
I. Podem ser determinísticos ou não determinísticos. 
II. Possuem uma pilha e o elemento na posição de saída desta 
equivale ao estado do autômato. 
III. Podem ser utilizados para identificar cadeias construídas por 
gramáticas livres de contexto e regulares. 
 
Estão corretas: 
 
Resposta Selecionada: d. 
As afirmações II e III. 
Respostas: a. 
As afirmações I e III. 
 b. 
A afirmação II apenas. 
 c. 
A afirmação III apenas. 
 d. 
As afirmações II e III. 
 e. 
Todas as afirmações. 
Comentário 
da resposta: 
Resposta: D 
Comentário: como a mudança de estado de um 
autômato de pilha é empilhar ou desempilhar um 
símbolo na pilha, eles não podem ser não 
 
determinísticos (não se empilha ou desempilha mais de 
um elemento de uma só vez).