Logo Passei Direto
Buscar
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.
User badge image
Desvendando com Questões

há 2 anos

Respostas

User badge image

Ed Verified user icon

há 12 meses

Para responder a essa pergunta, precisamos entender a Hierarquia de Chomsky e o que cada tipo de gramática representa: 1. Gramáticas do Tipo 0: Gramáticas recursivamente enumeráveis, reconhecidas por máquinas de Turing. 2. Gramáticas do Tipo 1: Gramáticas sensíveis ao contexto, reconhecidas por autômatos lineares limitados. 3. Gramáticas do Tipo 2: Gramáticas livres de contexto, reconhecidas por autômatos de pilha. 4. Gramáticas do Tipo 3: Gramáticas regulares, reconhecidas por autômatos finitos. Um autômato de pilha é capaz de reconhecer gramáticas do tipo 2 (livres de contexto) e também pode reconhecer gramáticas do tipo 3 (regulares), mas não é capaz de reconhecer gramáticas do tipo 1 (sensíveis ao contexto) ou do tipo 0 (recursivamente enumeráveis). Analisando as alternativas: a) Dos tipos 1, 2 e 3 - Incorreto, pois um autômato de pilha não reconhece gramáticas do tipo 1. b) Do tipo 1, apenas - Incorreto, pois um autômato de pilha não reconhece gramáticas do tipo 1. c) Do tipo 2, apenas - Correto, pois um autômato de pilha reconhece gramáticas do tipo 2. d) Do tipo 3, apenas - Incorreto, pois um autômato de pilha também reconhece gramáticas do tipo 2. e) Dos tipos 2 e 3 - Correto, pois um autômato de pilha reconhece gramáticas do tipo 2 e também do tipo 3. Portanto, as alternativas corretas são c) e e). Como a pergunta pede uma única resposta, a mais direta e específica é a c) Do tipo 2, apenas.

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

Um Autômato de Pilha pode ser utilizado como reconhecedor para uma gramática dos tipos 2 e 3, ou seja, as alternativas corretas são a letra C e a letra E. A letra A está incorreta, pois um Autômato de Pilha não pode ser utilizado como reconhecedor para uma gramática do tipo 1. A letra B está incorreta, pois um Autômato de Pilha pode ser utilizado como reconhecedor para uma gramática do tipo 1. A letra D está incorreta, pois um Autômato de Pilha pode ser utilizado como reconhecedor para uma gramática do tipo 3.

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:

Mais perguntas desse material

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

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