Teoria da Linguagem Formal e Autômatos

A teoria das linguagens formais e das máquinas abstratas que as reconhecem, fornecendo o vocabulário para descrever a complexidade de um padrão linguístico e quais algoritmos podem processá-lo.

Definition

A teoria da linguagem formal estuda conjuntos de cadeias de caracteres definidas por gramáticas, e a teoria dos autômatos estuda as máquinas abstratas que decidem a pertinência a esses conjuntos.

Scope

Abrange a hierarquia de Chomsky (linguagens regulares, livres de contexto, sensíveis ao contexto, recursivamente enumeráveis), as gramáticas correspondentes e os autômatos de reconhecimento — máquinas de estados finitos, autômatos de pilha e máquinas de Turing. Aborda propriedades de fechamento e decidibilidade relevantes para o processamento de linguagem e a questão de onde a linguagem natural se encaixa na hierarquia. Lemas de bombeamento e provas completas de complexidade são tratados como pano de fundo, em vez de conteúdo primário.

Core questions

• Qual autômato corresponde a cada nível da hierarquia de Chomsky?
• Onde a linguagem natural se encaixa na hierarquia e por que se argumenta que ela excede o poder livre de contexto?
• O que significa para uma classe de linguagem ser fechada sob uma operação e por que isso é importante para a engenharia?

Key concepts

• linguagem regular
• gramática livre de contexto
• gramática sensível ao contexto
• autômato de estados finitos
• autômato de pilha
• máquina de Turing
• propriedades de fechamento
• sensibilidade leve ao contexto

Key theories

Hierarquia de Chomsky

Quatro classes aninhadas de linguagens formais, cada uma gerada por um tipo de gramática restrita e reconhecida por um autômato correspondente, ordenando construções linguísticas pelo poder computacional exigido.

Correspondência gramática-autômato

Cada classe de gramática é comprovadamente equivalente a uma classe de máquina — gramáticas regulares a autômatos finitos, gramáticas livres de contexto a autômatos de pilha — ligando descrições gerativas a algoritmos de reconhecimento.

History

O artigo de Chomsky de 1956 introduziu a hierarquia como parte de um argumento de que os modelos de estados finitos eram inadequados para a linguagem natural. As décadas subsequentes formalizaram as correspondências dos autômatos, e linguistas computacionais mostraram mais tarde que a linguagem natural requer, no máximo, poder 'levemente sensível ao contexto', motivando formalismos gramaticais além dos livres de contexto.

Debates

A linguagem natural é livre de contexto?

Dependências cruzadas em linguagens como o alemão suíço foram usadas para argumentar que a linguagem natural excede o poder livre de contexto, levando à noção de sensibilidade leve ao contexto como o nível certo de expressividade.

Key figures

• Noam Chomsky
• John Hopcroft
• Jeffrey Ullman
• Stephen Kleene

Seminal works

• chomsky1956
• hopcroft2006

Frequently asked questions

Qual é a diferença entre uma linguagem regular e uma linguagem livre de contexto?

Linguagens regulares podem ser reconhecidas com memória finita por um autômato de estados finitos; linguagens livres de contexto podem exigir uma pilha (um autômato de pilha) para rastrear estruturas aninhadas, como parênteses balanceados ou orações encaixadas.