Logo Passei Direto
Buscar

Teoria da Computação

Outros
Analise as afirmacoes 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.
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.
User badge image
Desvendando com Questões

há 2 anos

User badge image
Desvendando com Questões

há 2 anos

Linguagens Formais e Automatos_Questionario 2
8 pág.

Linguagens Formais e Automatos_Questionario 2

UNIP

Respostas

User badge image

Ed Verified user icon

ano passado

Vamos analisar cada uma das afirmações sobre o Formalismo de Backus-Naur: I. Só pode ser utilizado para gramáticas livres de contexto. Falso. O Formalismo de Backus-Naur (BNF) é frequentemente utilizado para descrever gramáticas livres de contexto, mas não se limita a elas. Ele pode ser adaptado para outras classes de gramáticas. II. Diferente das expressões regulares, não se baseia em operações, sendo apenas uma forma mais simplificada de representar uma gramática. Falso. O BNF é uma forma de descrever gramáticas, mas não é correto afirmar que não se baseia em operações. Ele utiliza produções que podem ser vistas como operações de substituição. III. Gramáticas representadas nesta forma não podem ser representadas na forma de um autômato. Falso. As gramáticas que podem ser descritas pelo BNF, especialmente as gramáticas livres de contexto, podem ser representadas por autômatos, como autômatos de pilha. Agora, vamos verificar as alternativas: a. As afirmações I e III. (Falso) b. A afirmação II apenas. (Falso) c. A afirmação III apenas. (Falso) d. As afirmações II e III. (Falso) e. Todas as afirmações. (Falso) Nenhuma das afirmações está correta. Portanto, não há uma alternativa correta entre as opções apresentadas.

Essa resposta te ajudou?

0
Dislike0
details

Libere essa resposta sem enrolação!

Craque NetoCraque Neto

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

User badge image

Ed Verified user icon

há 2 anos

O Formalismo de Backus-Naur é uma notação utilizada para descrever gramáticas livres de contexto. Sobre as afirmações apresentadas, podemos afirmar que: I. A afirmação está correta. O Formalismo de Backus-Naur é utilizado para descrever gramáticas livres de contexto. II. A afirmação está incorreta. O Formalismo de Backus-Naur se baseia em operações, como a concatenação e a alternância, para representar uma gramática. III. A afirmação está incorreta. Gramáticas representadas nesta forma podem ser representadas na forma de um autômato. Portanto, a alternativa correta é a letra A) As afirmações I e III.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Linguagens Formais e Automatos_Questionario 2
8 pág.

Linguagens Formais e Automatos_Questionario 2

UNIP

Mais perguntas desse material

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)_________."


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.

Em relação à memória auxiliar em um Autômato (finito ou de pilha), assinale a alternativa correta:


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.

Considere a Hierarquia de Chomsky como apresentada na imagem. Um Autômato de Pilha pode ser utilizado como reconhecedor para uma gramática:


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.

Uma Linguagem Irrestrita apresenta como característica das regras de substituição da sua gramática:


a. Um símbolo terminal só pode ser substituído por um símbolo terminal, um não terminal e outro terminal, nesta 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).

Indique a alternativa incorreta sobre Máquinas de Turing.


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.

Indique a alternativa correta sobre Autômatos Finitos não Determinísticos.


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.

Indique a alternativa correta sobre 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.
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.

Uma Máquina de Turing com fita limitada à esquerda irá reconhecer Linguagens:


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.

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.
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.

Mais conteúdos dessa disciplina