A Hierarquia de Chomsky

A hierarquia de Chomsky organiza as linguagens formais em quatro classes aninhadas, cada uma definida por uma restrição nas regras gramaticais e correspondendo a um tipo distinto de máquina abstrata.

Definition

A hierarquia de Chomsky é uma classificação de gramáticas formais por restrições progressivamente mais fortes em suas regras de produção, resultando nas classes de linguagem regular, livre de contexto, sensível ao contexto e recursivamente enumerável em uma cadeia de inclusões estritas.

Scope

Este tópico aborda os quatro tipos de gramática — irrestrita, sensível ao contexto, livre de contexto e regular — sua contenção estrita e o modelo de autômato correspondente a cada nível, ou seja, a máquina de Turing, o autômato linearmente limitado, o autômato de pilha e o autômato finito, juntamente com as propriedades de fechamento e decidibilidade que separam os níveis.

Core questions

• Como as restrições nas regras gramaticais se traduzem em limites de memória e poder computacional?
• Por que cada nível da hierarquia está estritamente contido no próximo?
• Qual modelo de autômato corresponde a cada tipo de gramática?
• Como as propriedades de decidibilidade e fechamento mudam à medida que se avança na hierarquia?

Key theories

Correspondência gramática–máquina

Cada classe de gramática é reconhecida por um modelo de máquina específico — regular por autômatos finitos, livre de contexto por autômatos de pilha, sensível ao contexto por autômatos linearmente limitados e irrestrita por máquinas de Turing — ligando descrições generativas e operacionais da computação.

Inclusão estrita das classes de linguagem

Cada nível contém propriamente o nível abaixo dele, evidenciado por linguagens separadoras concretas, de modo que a hierarquia é uma verdadeira escada de poder expressivo crescente, em vez de uma coleção de descrições equivalentes.

Clinical relevance

A hierarquia é o mapa organizador da teoria da linguagem formal: ela informa aos projetistas de linguagens de programação, linguagens de consulta e especificações de protocolo quanta maquinaria uma dada classe de padrões requer, e enquadra a fronteira entre o que é decidível e o que é apenas reconhecível.

History

Chomsky propôs a hierarquia no final da década de 1950 enquanto buscava modelos formais da sintaxe da linguagem natural, e as correspondências de máquina foram estabelecidas à medida que a teoria dos autômatos amadureceu ao longo da década de 1960, com os autômatos linearmente limitados introduzidos por Myhill e o nível sensível ao contexto clarificado por Kuroda.

Key figures

• Noam Chomsky
• Marcel-Paul Schützenberger
• John Myhill

Seminal works

• hopcroft2006
• sipser2013

Frequently asked questions

Quais são os quatro níveis da hierarquia de Chomsky?

Do menos para o mais poderoso, são as linguagens regulares (Tipo 3), as linguagens livres de contexto (Tipo 2), as linguagens sensíveis ao contexto (Tipo 1) e as linguagens recursivamente enumeráveis (Tipo 0). Cada nível relaxa as restrições nas regras gramaticais e corresponde a uma máquina com mais memória.

A linguagem natural é capturada pela hierarquia de Chomsky?

A hierarquia foi originalmente motivada pela linguística, mas a maioria dos linguistas conclui que as linguagens naturais não são livres de contexto, situando-se em um nível frequentemente chamado de levemente sensível ao contexto. A hierarquia permanece fundamental na ciência da computação, embora a linguagem humana se encaixe nela apenas de forma frouxa.