Teoria dos autômatos é o estudo das máquinas abstratas ou autômatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos. É objeto de estudo tanto da Ciência da Computação Teórica como da Matemática Discreta. A palavra autômato vem da palavra grega αὐτόματα que significa “autuação” (em tradução livre), isto é, sem influência externa. A figura ao lado ilustra uma máquina de estados finito, que pertence a uma variedade bem conhecida de autômato. Este autômato consiste em estados (representados na figura por círculos), e transições (representadas por setas). Quando o autômato recebe um símbolo de entrada, ele faz uma transição (ou salto) para outro estado, de acordo com sua função de transição (que tem como entradas o estado atual e o símbolo recente).
Teoria dos autômatos também está profundamente relacionada à teoria das linguagens formais. Um autômato é uma representação finita de uma linguagem formal que pode ser um conjunto infinito. Autômatos são frequentemente classificados pela classe das linguagens formais que são capazes de reconhecer, tipicamente ilustrado pela hierarquia de Chomsky, que descreve as relações entre várias línguas e tipos de lógica formalizada.thumb|258x258px|Um exemplo de autômato. O estudo de propriedades matemáticas destes autômatos é a teoria dos autômatosAutômatos desempenham um papel importante em teoria da computação, elaboração de compiladores, inteligência artificial, análise sintática e verificação formal.
Autômatos Segue uma definição introdutória de um tipo de autômato, que ajuda na compreensão dos conceitos essenciais envolvidos na teoria dos autômatos.
Descrição Muito Informal Um autômato é uma construção feita de estados, projetado para determinar se a entrada pode ser aceita ou rejeitada. Parece muito com um jogo de tabuleiro básico em que cada espaço no tabuleiro representa um estado. Cada estado tem informações sobre o que fazer quando uma entrada é recebida pela máquina (novamente, parece como o que fazer quando você cai num dos espaços em um popular jogo de tabuleiro). Quando a máquina recebe um nova entrada, ela analisa o estado e escolhe um novo local baseada na informações sobre o que fazer ao receber essa entrada nesse estado. Quando não há mais entradas, o autômato para e o espaço onde está quando conclui determina se o autômato aceita ou rejeita esse conjunto específico de entradas.
Descrição Informal
Um autômato executa (ou roda) quando lhe é dada uma sequência de entradas (individualmente) em passos de tempo discretos. Um autômato processa uma entrada que é obtida a partir de um conjunto de símbolos ou letras, que é chamado de alfabeto. Os símbolos recebidos pelo autômato como entrada, em qualquer etapa (ou passo) são uma sequência de símbolos chamados de palavras. Um autômato contém um conjunto finito de estados. Para cada instante durante a execução, o autômato está em um de seus estados. Ao receber uma nova entrada, ele se move para outro estado (ou faz a transição) baseado numa função que tem o estado atual e o símbolo como parâmetros. Esta função é chamada de função de transição. O autômato lê os símbolos da palavra de entrada, um após o outro, e faz a transição de estado para estado, de acordo com a função de transição, até a palavra ser totalmente lida. Uma vez que a palavra de entrada foi lida, diz-se que o autômato deve parar. O estado no qual o autômato para é chamado de estado final. Dependendo do estado final, o autômato pode aceitar ou rejeitar uma palavra de entrada. Existe um subconjunto de estados do autômato, que é definido como o conjunto de estados de aceitação. Se o estado final é um estado de aceitação, então o autômato aceita a palavra. Caso contrário, a palavra é rejeitada. O conjunto de todas as palavras aceitas por um autômato é chamado de linguagem reconhecida pelo autômato. Qualquer subconjunto da linguagem de um autômato é uma linguagem reconhecida pelo autômato.
Em suma, um autômato é um objeto matemático que toma uma palavra como entrada e decide se a aceita ou rejeita. Como todos os problemas computacionais são redutíveis para o problema de aceitação/rejeição de palavras, (todas as instâncias do problema podem ser representadas por um tamanho finito de símbolos), a teoria dos autômatos desempenha um importante papel na teoria computacional.
Definição formal Autômatos Definição de máquina de estados finita Um autômato determinístico finito é representado formalmente por uma 5-tupla (Q,Σ,δ,q0,F), onde: Q é um conjunto finito de estados. Σ é um conjunto finito de símbolos (símbolo), chamado de alfabeto do autômato. δ é a função de transição, isto é, δ: Q x Σ → Q. q0 é o estado inicial, isto é, o estado do autômato antes de qualquer entrada ser processada, onde q0 ∈ Q. F é um conjunto de estados de Q (isto é, F ⊆ Q) chamado de estados de aceitação.
Palavra de entrada Um autômato lê uma string (cadeia de caracteres) finita de símbolos a1,a2,...., an, onde ai ∈ Σ, que é chamada de palavra de entrada. O conjunto de todas as palavras é denotado por Σ*.
Execução A execução de um autômato sobre uma palavra de entrada w = a1,a2,...., an ∈ Σ*, é uma sequência de estados q0, q1,q2,...., qn, onde qi ∈ Q tal que q0 é o estado inicial e qi = δ(qi-1,ai) para 0 < i ≤ n. Em outras palavras, no começo o autômato está no estado inicial q0, e então o autômato lê símbolos da palavra de entrada sequencialmente. Quando o autômato lê o símbolo ai ele pula para o estado qi = δ(qi-1,ai). Diz-se que qn é o estado final da execução.
Palavra de aceitação Uma palavra w ∈ Σ* é aceita pelo autômato se qn ∈ F.
Linguagem reconhecida Um autômato pode reconhecer uma linguagem formal. A linguagem L ⊆ Σ* reconhecida por um autômato é o conjunto de todas as palavras que são aceitas pelo autômato.
Linguagens reconhecíveis As linguagens reconhecíveis são o conjunto de linguagens que são reconhecidas por algum autômato. Para a definição acima de autômatos, as linguagens reconhecíveis são linguagens regulares. Para diferentes definições de autômatos, a definição de linguagens reconhecíveis é diferente.
Definições variantes de autômatos
Autômatos são definidos para estudar máquinas úteis sobre formalismo matemático. Então, a definição de um autômato é aberta a variações de acordo com a “máquina do mundo real”, que nós queremos modelar usando o autômato. Há estudos das muitas variações de autômatos. A principal variante, descrita acima, é chamada de autômato finito determinístico. Seguem variações populares da definição dos diferentes componentes de autômatos.
Entrada Entrada finita: Um autômato que aceita apenas sequências finitas de símbolos. A definição introdutória acima engloba apenas palavras finitas. Entrada infinita: Um autômato que aceita palavras infinitas (ω-palavras). Tais autômatos são chamados de ω-autômatos. Entrada palavra árvore: A entrada pode ser uma árvore de símbolos ao invés de uma sequência de símbolos. Neste caso, após ler cada símbolo, o autômato lê todos os símbolos sucessores na árvore de entrada. Diz-se que o autômato faz uma cópia dele mesmo para cada sucessor, e cada cópia executa um símbolo sucessor do estado de acordo com a relação de transição do autômato. Este autômato é chamado de autômato de árvore. Entrada árvore infinita: As duas extensões acima podem ser combinadas, então o autômato lê uma estrutura de árvore com (in)finitos desvios. Este autômato é chamado de autômato de árvore infinita.
Estados Estados finitos: Um autômato que contém apenas um número finito de estados. A definição introdutória acima descreve autômatos com números finitos de estados. Estados infinitos: Um autômato que pode não ter um número finito de estados, ou até mesmo um número contável de estados. Por exemplo, o autômato finito quantum ou autômato topológico tem um número infinito e incontável de estados. Pilha de memória: Um autômato pode também conter uma memória extra no formato de pilha, em que símbolos podem ser colocados e retirados. Este tipo de autômato é chamado de Autômato Pushdown (Autômato com pilha).
Função de transição Determinística: Para um dado estado atual e um símbolo de entrada, se um autômato pode pular para um e apenas um estado, então ele é um autômato determinístico. Não-Determinismo: Um autômato que, após ler um símbolo de entrada, pode pular para qualquer um de vários estado, decidido por sua relação de transição. Note que o termo função de transição é substituído por relação de transição: O autômato não-determinísticamente decide pular para uma das opções permitidas. Tais autômatos são chamado de autômatos não-determinísticos. Alternamento: Esta ideia é muito semelhante ao autômato árvore, mas ortogonal. O autômato pode executar suas múltiplas cópias sobre o mesmo símbolo a ser lido. Tais autômatos são chamados de autômato finito alternado. A condição de aceitação deve satisfazer todas as execuções de tais cópias para aceitar a entrada.
Condição de aceitação Aceitação de palavras finitas: Como descrito na definição informal acima. Aceitação de palavras infinitas: Um ω-autômato não pode ter estados finais, já que palavras infinitas nunca terminam. Preferencialmente, aceitação da palavra é decidida analisando as sequências infinitas dos estados visitados durante a execução. Aceitação probabilística: Um autômato não precisa estritamente aceitar ou rejeitar uma entrada. Ele pode aceitar a entrada com uma probabilidade entre zero e um. Por exemplo, autômato finito quantum, autômato geométrico e autômato métrico têm aceitação probabilística.
Diferentes combinações das variações acima produzem mais classe de autômato.
Teoria dos Autômatos
Teoria de autômatos é um assunto que estuda as propriedades de vários tipos de autômatos. Por exemplo, as questões a seguir são relacionadas a um dado tipo de autômatos.
Qual classe de linguagens formais é reconhecível por algum tipo de autômato? (linguagens reconhecíveis) Certos autômatos são fechados sobre a união, interseção ou complemento de linguagens formais? (propriedades de fechamento) Quão expressivo é um tipo de autômato em termos de reconhecer classe de linguagens formais? E, quanto ao poder relativo de expressividade? (hierarquia de linguagem)
Teoria dos autômatos também estuda se existe algum algoritmo efetivo ou não para resolver problemas semelhantes à seguinte lista:
Um autômato aceita alguma palavra de entrada? (verificação de vazio – vacuidade) É possível transformar um dado autômato não-determinístico em um autômato determinístico sem mudar a linguagem reconhecível? (determinização) Para uma dada linguagem formal, qual é o menor autômato que a reconhece? (Minimização).
Classe de Autômatos
Segue uma lista incompleta de tipos de autômatos.
Autômatos Linguagem reconhecível Autômatos finitos determinísticos(AFD) Linguagens regulares Autômatos Finitos Não-determinísticos(AFN) Linguagens regulares Autômatos Finitos Não-determinísticos com ε-transições (FND-ε or ε-AFN) Linguagens regulares Autômato com Pilha (AP) Linguagens livre de contexto Autômato linearmente limitado (ALL) Linguagem sensível ao contexto Máquinas de Turing Linguagem recursivamente enumerável Autômatos temporizado Autômato de Büchi Linguagens ω-limite Autômatos Não-determinístico de Büchi Linguagens ω-regular Autômatos Não-determinístico/Determinístico de Rabin Linguagens ω-regular Autômatos Não-determinístico/Determinístico de Street Linguagens ω-regular Autômatos Não-determinístico/Determinístico de Paridade Linguagens ω-regular Autômatos Não-determinístico/Determinístico de Muller Linguagens ω-regular
Autômatos discretos, contínuos e híbridos
Geralmente teoria dos autômatos descreve os estados de máquinas abstratas, mas existem autômatos analógicos, contínuos ou híbridos (discreto-contínuo), que usam dados analógicos, tempo contínuo, ou ambos.
Hierarquia em termos de poderes