A Hierarquia de Chomsky é uma classificação das gramáticas formais, proposta pelo linguista Noam Chomsky, que divide as gramáticas em 4 classes. Ne...

A Hierarquia de Chomsky é uma classificação das gramáticas formais, proposta pelo linguista Noam Chomsky, que divide as gramáticas em 4 classes. Nesse sentido, Linguagens livres de

a) contexto são aquelas que podem ser reconhecidas por um autômato finito determinístico.
b) contexto são aquelas que podem ser reconhecidas por um autômato finito não determinístico.
c) tipo 1 são aquelas que podem ser reconhecidas por um autômato finito determinístico.
d) tipo 0 são aquelas que podem ser reconhecidas por uma máquina de Turing.
e) tipo 3 são aquelas que podem ser reconhecidas por uma gramática regular.

Compiladores

•

Outros

0

1

Aprendendo Através de Exercícios

26/11/2023

Essa pergunta também está no material:

1 pág.

Compiladores

Angel Lopes

💡 1 Resposta

Ed

26.11.2023

A alternativa correta é a letra "d) tipo 0 são aquelas que podem ser reconhecidas por uma máquina de Turing". As linguagens livres de contexto são aquelas que podem ser geradas por uma gramática livre de contexto, que é uma gramática formal que possui regras de produção que substituem um símbolo não-terminal por uma sequência de símbolos, sem levar em conta o contexto em que o símbolo aparece. As linguagens tipo 0 são as mais gerais, e podem ser reconhecidas por uma máquina de Turing, que é um modelo teórico de computação que pode simular qualquer algoritmo computacional.

0