Questões de Autômatos

Questão 2324902

• Banca: IFB
• Órgão: IFB
• Ano: 2017
• Provas: IFB - 2017 - IFB - Professor - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Autômatos

Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita – hierarquia de Chomsky).

• A. Gramáticas irrestritas > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas regulares.
• B. Gramáticas regulares > Gramáticas livres de contexto > Gramáticas sensíveis ao contexto > Gramáticas irrestritas.
• C. Gramáticas livres de contexto > Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas regulares.
• D. Gramáticas irrestritas > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas regulares.
• E. Gramáticas regulares > Gramáticas sensíveis ao contexto > Gramáticas livres de contexto > Gramáticas irrestritas.

Gabarito: D

Comentários

• Gabarito D

  Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica.

  A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma linguagem de tipo n - 1.

   

  Tipo-0 Irrestrita

  Tipo-1 Sensível ao contexto

  Tipo-2 Livre de contexto

  Tipo-3 Regular

   

   

  "Retroceder Nunca Render-se Jamais !"
  Força e Fé !
  Fortuna Audaces Sequitur !

• Força Guerreiro!!!!!!