Autômatos e Linguagens Formais
A teoria de autômatos e linguagens formais estuda máquinas idealizadas de poder crescente e as classes de cadeias, ou linguagens, que cada uma pode reconhecer, fornecendo uma descrição matemática precisa do que conta como um padrão e do que é necessário para detectá-lo.
Definition
Uma linguagem formal é um conjunto de cadeias finitas sobre um alfabeto fixo, e um autômato é um dispositivo computacional abstrato cujas computações de aceitação definem tal linguagem; a área classifica as linguagens pelo tipo mais simples de autômato ou gramática que as gera ou reconhece.
Scope
Esta área abrange autômatos finitos e linguagens regulares, autômatos de pilha e linguagens livres de contexto, a hierarquia de Chomsky que relaciona gramáticas a modelos de máquina, propriedades de fechamento e decisão de classes de linguagem, e autômatos que processam palavras e árvores infinitas, juntamente com as caracterizações algébricas e lógicas que os acompanham.
Sub-topics
Core questions
- Quais linguagens uma máquina com memória finita pode reconhecer e o que ela não pode reconhecer?
- Como as gramáticas e os modelos de máquina se correspondem nos níveis da hierarquia de Chomsky?
- Quais questões sobre uma classe de linguagem, como vazio ou equivalência, são algoritmicamente decidíveis?
- Como os autômatos se estendem a palavras e árvores infinitas, e por que isso é importante para a verificação?
Key theories
- Equivalência de autômatos finitos determinísticos e não determinísticos
- Todo autômato finito não determinístico pode ser convertido pela construção de subconjuntos em um determinístico que aceita a mesma linguagem, de modo que o não determinismo não adiciona poder de reconhecimento no nível de estado finito, embora possa ser exponencialmente mais conciso.
- Teorema de Kleene
- As linguagens reconhecidas por autômatos finitos são exatamente as linguagens regulares descritas por expressões regulares, unindo as visões de máquina, algébrica e gramatical da classe de linguagem mais simples.
- A hierarquia de Chomsky
- Linguagens regulares, livres de contexto, sensíveis ao contexto e recursivamente enumeráveis formam uma cadeia de inclusão estrita, cada nível correspondendo a um tipo de gramática e a um modelo de autômato de estrutura de memória correspondente.
Clinical relevance
Autômatos finitos e expressões regulares impulsionam a análise lexical em compiladores, busca de texto e especificação de protocolo, enquanto gramáticas livres de contexto sustentam a análise sintática de linguagens de programação; autômatos sobre objetos infinitos formam o núcleo algorítmico da verificação de modelos, onde um sistema é verificado em relação a uma especificação de lógica temporal.
History
Modelos de estados finitos emergiram das redes neurais de McCulloch e Pitts na década de 1940 e receberam forma teórica de linguagem por Kleene por volta de 1951. Rabin e Scott introduziram autômatos não determinísticos em 1959, enquanto as gramáticas de Chomsky do final da década de 1950 organizaram as classes de linguagem na hierarquia que ainda estrutura o assunto.
Key figures
- Stephen Kleene
- Michael Rabin
- Dana Scott
- Noam Chomsky
Related topics
Seminal works
- rabinScott1959
- sipser2013
- hopcroft2006
Frequently asked questions
- Por que um autômato finito não consegue reconhecer parênteses balanceados?
- Reconhecer aninhamentos arbitrariamente profundos requer contar quantas aberturas ainda não foram correspondidas, o que pode exceder qualquer número fixo de estados. Um autômato finito tem apenas memória limitada, então essa capacidade de contagem está um nível acima, com autômatos de pilha e linguagens livres de contexto.
- Qual é o benefício prático da teoria das linguagens formais?
- Ela informa aos engenheiros quais padrões uma determinada ferramenta pode expressar. Expressões regulares são suficientes para tokens, mas não para estruturas aninhadas, razão pela qual os compiladores dividem o trabalho entre um analisador léxico regular e um analisador sintático livre de contexto, e por que as ferramentas de verificação dependem de autômatos sobre palavras infinitas.