Teoria dos autômatos

Aspeto mover para a barra lateral ocultar

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.

Assuntos relacionados a teoria dos autômatos.

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.

Um exemplo de autômato. O estudo de propriedades matemáticas destes autômatos é a teoria dos autômatos

Autô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: 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 Estados Função de transição Condição de aceitação

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.

Teoria dos autômatos também estuda se existe algum algoritmo efetivo ou não para resolver problemas semelhantes à seguinte lista:

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

Segue uma hierarquia incompleta, em termos de poder, dos diferentes tipos de máquinas virtuais. A hierarquia reflete as categorias aninhadas que as máquinas são capazes de aceitar.

Autômatos
Autômato Finito Determinístico(AFD) -- Menor Poder

(mesmo poder)    ||   (mesmo poder)

Máquina de estados finitos não determinística (AFND)

(acima é mais fraco)    ∩    (abaixo é mais forte)

Autômato com pilha determinístico (APD-l)

com uma pilha auxiliar

∩

Autômato com pilha Não-Determinístico (APND)

com uma pilha auxiliar

∩

Autômato linearmente limitado (ALL)

∩

Autômato com pilha determinístico (APD-II)

com duas pilhas auxiliares

||

Autômato com pilha Não-Determinístico (APND-II)

com duas pilhas auxiliares

||

Máquina de Turing Determinística (MTD)

||

Máquina de Turing Não-Determinística (MTND)

||

Máquina de Turing Probabilística (MTP)

||

Máquina de Turing multifita (MTMF)

||

Máquina de Turing multidimensional (MTMD)

Aplicações

Cada modelo em teoria dos autômatos desempenha papéis importantes em muitas áreas aplicadas. Autômatos finitos são usados em processamento de texto, compiladores e projeto de hardware. Gramáticas livres de contexto (GLCs) são usadas em linguagens de programação e inteligência artificial. Originalmente, GLCs eram usadas no estudo de linguagens humanas. Autômatos celulares são usados no campo da biologia, o exemplo mais comum é o de Jogo da Vida de John Conway. Outros exemplos que podiam ser explicados usando teoria dos autômatos em biologia incluem crescimento de pinhas e molusco e padrões de pigmentação. Indo mais longe, uma teoria que sugere que todo o universo é computado por algum tipo de autômato discreto é defendida por cientistas. A ideia vem do trabalho de Konrad Zuse, e foi popularizada na América por Edward Fredkin.

Simuladores de autômatos

Simuladores de autômatos são ferramentas pedagógicas usadas para ensinar, aprender e pesquisar teoria dos autômatos. Um simulador de autômato tem como entrada a descrição de um autômato e então simula seu funcionamento para uma string arbitrária como entrada. A descrição do autômato pode ser inserida de várias formas. Um autômato pode ser definido por uma linguagem simbólica ou sua especificação pode ser inserida em uma forma predefinida ou seu diagrama de transição pode ser projetado no clicar e arrastar do mouse. Simuladores de autômatos bem conhecidos incluem Turing’s World, JFLAP, VAS, TAGS e SimStudio.

Conexão com a teoria das categorias

Pode-se definir muitas categorias diferentes de autômatos seguindo a classificação de autômatos em diferentes tipos, descrita na seção anterior. A categoria matemática dos autômatos determinísticos, máquinas sequenciais ou autômatos sequenciais, e máquinas de Turing com homomorfismos de autômatos, que define as setas entre autômatos é uma categoria fechada cartesiana, que tem ambos, co-limites e limites categóricos. Um homomorfismo de autômato mapeia uma 5-tupla de um autômato Ai em uma 5-tupla de outro autômato Aj. Homomorfismo de autômatos também pode ser considerado como transformações de autômatos ou homomorfismos semigrupo, quando o espaço do estado, S, do autômato é definido como um semigrupo Sg. Monoides são também considerados como um ambiente propício para autômatos em categorias monoides.

Categorias de autômatos variáveis

Pode-se também definir um autômato variável, no sentido de Norbert Wiener em seu livro “Human Use of Human Beings” pelos endomorfismos Ai-->Ai. Então, pode-se mostrar que estes homomorfismos de autômatos variáveis formam um grupo matemático. No caso do não-determinístico, ou outros tipos complexos de autômatos, o último conjunto de endomorfismo pode tornar-se, contudo, um grupóide de autômato variável. Portanto, no caso mais geral, categorias de autômatos variáveis de qualquer tipo são categorias de grupóides ou categorias grupóides. Além disso, a categoria de autômatos reversíveis é então uma 2-categoria, e também uma subcategoria da 2-categoria de grupóides, ou a categoria grupóide.

Referências

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman – Introdução à Teoria de Autômatos, Linguagens e Computação (2ª Edição).

  1. ↑ Chakraborty, P., Saxena, P. C., Katti, C. P. 2011. Fifty Years of Automata Simulation: A Review. ACM Inroads, 2(4):59–70. http://dl.acm.org/citation.cfm?id=2038893&dl=ACM&coll=DL&CFID=65021406&CFTOKEN=86634854
  2. ↑ Jirí Adámek and Vera Trnková. 1990. Automata and Algebras in Categories. Kluwer Academic Publishers:Dordrecht and Prague
  3. ↑ S. Mac Lane, Categories for the Working Mathematician, Springer, New York (1971)
  4. ↑ http://planetmath.org/encyclopedia/CartesianClosedCategory.html Cartesian closed category
  5. ↑ http://planetmath.org/encyclopedia/SequentialMachine3.html The Category of Automata
  6. ↑ http://www.csee.wvu.edu/~jworthing/asl2010.pdf James Worthington.2010.Determinizing, Forgetting, and Automata in Monoidal Categories. ASL North American Annual Meeting,March 17, 2010
  7. ↑ Aguiar, M. and Mahajan, S.2010. "Monoidal Functors, Species, and Hopf Algebras".
  8. ↑ Meseguer, J., Montanari, U.: 1990 Petri nets are monoids. Information and Computation 88:105–155


Softwares