Hierarquia chomsky

HIERARQUIA DE CHOMSKY

Professor Carlos Hairon

 Noam Chomsky
•

Nasceu em 7 de dezembro de 1928, na Filadélfia

•

Avram Noam Chomsky é um linguista, filósofo e ativista político estadunidense

•

Professor de Linguística no Instituto de Tecnologia de Massachusetts

•

Autor de trabalhos fundamentais sobre as propriedades matemáticas das linguagens formais

•

Hierarquia de Chomsky (1959): o Chomsky é famoso por pesquisar vários tipos de linguagens formais procurando entender se poderiam ser capazes de capturar as propriedades -chave das línguas humanas  A hierarquia de Chomsky
•

Divide as gramáticas formais em classes com poder expressivo crescente, por exemplo, cada classe sucessiva pode gerar um conjunto mais amplo de linguagens formais que a classe imediatamente anterior.

•

Classificação de gramáticas formais que possui 4 níveis (Tipos 0, 1, 2 e 3)

•

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: o O nível 2 é utilizado em análise sintática (computação) o 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 superconjunto do próximo

 A hierarquia de Chomsky
•

As quatro classes de linguagens e suas inclusões próprias constituem a
Hierarquia de
Chomsky

 Linguagens enumeráveis recursivamente (Tipo 0):
•

Tipo de linguagem formal, também conhecida como Turing -reconhecível

•

Definições de linguagens enumeráveis recursivamente formais:

o É um subconjunto recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem; o É uma linguagem formal para a qual existe uma máquina de Turing que irá enumerar todas as cadeias válidas da linguagem; o Uma linguagem recursivamente enumerável é uma linguagem formal para a qual