Autômatos Finitos e Linguagens Regulares

Autômatos finitos são as máquinas computacionais mais simples, lendo a entrada um símbolo por vez usando apenas um número limitado de estados internos, e as linguagens que eles reconhecem são precisamente as linguagens regulares.

Definition

Um autômato finito é uma máquina com um conjunto finito de estados, uma função de transição sobre símbolos de entrada, um estado inicial e estados de aceitação; ele aceita uma cadeia se a leitura da cadeia o leva do estado inicial para um estado de aceitação, e o conjunto de cadeias aceitas é sua linguagem.

Scope

Este tópico abrange autômatos finitos determinísticos e não determinísticos, sua equivalência via construção de subconjuntos, expressões regulares e o teorema de Kleene, o teorema de Myhill–Nerode e minimização de estados, propriedades de fechamento de linguagens regulares, e o lema do bombeamento usado para provar que certas linguagens não são regulares.

Core questions

• Quais linguagens podem ser reconhecidas usando apenas uma quantidade fixa e finita de memória?
• Por que autômatos finitos determinísticos e não determinísticos são igualmente poderosos?
• Como se pode provar que uma linguagem específica não é regular?
• Qual é o menor autômato que reconhece uma dada linguagem regular?

Key theories

Construção de subconjuntos

Qualquer autômato finito não determinístico pode ser simulado por um determinístico cujos estados são conjuntos dos estados originais, provando que os dois modelos reconhecem exatamente as mesmas linguagens.

Teorema de Kleene

Uma linguagem é reconhecida por um autômato finito se e somente se for descrita por uma expressão regular, estabelecendo a equivalência das descrições de máquina e algébricas de linguagens regulares.

Teorema de Myhill–Nerode

Uma linguagem é regular exatamente quando sua relação de indistinguibilidade de cadeias possui um número finito de classes, e essas classes determinam o autômato determinístico mínimo único para a linguagem.

Clinical relevance

Autômatos finitos são o motor por trás da correspondência de expressões regulares, scanners e analisadores lexicais em compiladores, busca e substituição em editores de texto, e detecção de padrões em sistemas de intrusão de rede, onde o reconhecimento com memória limitada torna o processamento rápido e previsível.

History

Com base no modelo de redes neurais de McCulloch e Pitts de 1943, Kleene caracterizou os eventos que autômatos finitos podem representar por volta de 1951, e Rabin e Scott formalizaram autômatos não determinísticos e seus problemas de decisão em 1959, trabalho posteriormente reconhecido com o Prêmio Turing.

Key figures

• Stephen Kleene
• Michael Rabin
• Dana Scott
• Anil Nerode

Seminal works

• rabinScott1959
• sipser2013

Frequently asked questions

Como se demonstra que uma linguagem não é regular?

A ferramenta mais comum é o lema do bombeamento, que afirma que toda cadeia suficientemente longa em uma linguagem regular contém uma subcadeia que pode ser repetida qualquer número de vezes, permanecendo na linguagem. Encontrar uma cadeia que não pode ser bombeada dessa forma prova que a linguagem não é regular; o teorema de Myhill–Nerode oferece um argumento alternativo ao exibir infinitos prefixos distinguíveis.

Se autômatos não determinísticos não são mais poderosos, por que usá-los?

Eles são frequentemente muito menores e mais fáceis de projetar ou de derivar de uma expressão regular. A construção de subconjuntos pode convertê-los para a forma determinística quando necessário, a um possível custo exponencial no número de estados, então o não determinismo é uma ferramenta de especificação conveniente, em vez de um aumento no poder de reconhecimento.