Chomsky

Hierarquia de Chomsky

Pedro Colen Cardoso

Hierarquia de Chomsky
A Hierarquia

No campo de ciência da computação que estuda linguagens formais, a hierarquia de Chomsky é a classificação de gramáticas formais descrita por Noam Chomsky em 1956. Essa hierarquia é dividida em 4 níveis indo de 0 até 3 e cada nível da classificação descreve o nível de liberdade da linguagem. Abaixo estão especificados os quatro níveis da hierarquia:

Tipo 0: As gramáticas classificas com esse nível são conhecidas como ‘Gramáticas irrestritas’, são aquelas que não possuem limitações. Inclui todas as linguagens formais e gera exatamente o grupo com todas as linguagens que podem ser identificadas pela maquina de Turing.
Tipo 1: As ‘Gramáticas sensíveis ao contexto’ estão sujeitas a regra de substituição que diz que ‘nenhuma substituição de palavra de uma frase pode reduzir o tamanha da frase’, desta forma limitamos esse tipo de operação. Esse grupo gramatical forma o conjunto que é reconhecido por autômatos lineares limitados (uma forma não determinística da maquina de Turing que esta sujeita ao tamanho da palavra).
Tipo 2: As gramáticas deste tipo são as ‘Gramáticas livre de contexto’. Estas são a base teórica para a maioria das linguagens de programação e são definidas por uma regra que especifica as substituições que podem ser feitas neste tipo de gramática (veja o quadro abaixo para forma geral da regra). As gramáticas livre de contexto são reconhecidas pelos chamados autômatos com pilha.
Tipo 3: Nas gramáticas de tipo 3 temos as chamadas ‘Gramáticas Regulares’ que são reconhecidas pelos autômatos de estados finitos. Neste nível as linguagens possuem regras bem restritas o que torna fácil o seu reconhecimento. As gramáticas regulares são muito importante para a construção de compiladores pelo fato de que, de toda gramática regular podemos tirar expressões regulares*.

Abaixo temos