Autômatos – Definições e Conceitos Gerais

Euclides Palma Paim
Escola Politécnica de Computação Aplicada
Universidade do Vale do Rio dos Sinos – Unisinos
São Leopoldo, Brasil
euclidespaim@gmail.com

.

Abstract—This document is a short explanation of automata
theory, presents concepts about the theory of computation,
abroad formal definitions of deterministic and nondeterministic
automaton and illustrate a practical example of modeling that
uses a finite automata. This paper describes a hypothetical
implementation of a system cash machine and its operations.
Keywords—automata; finite state machines; theory of
computation

.

I. INTRODUÇÃO
Teoria dos autômatos é um ramo da ciência da computação
que estabeleceu suas raízes durante o século passado quando
matemáticos desenvolveram tanto teórica como literalmente
máquinas que imitavam certas características humanas
realizando cálculos mais rápidos e precisos. A palavra
autômato esta intrinsicamente ligada com a palavra automação
e indica execução automática de processos específicos
relacionados à produção. Em outras palavras, a teoria dos
autômatos lida com a lógica computacional de máquinas,
conhecidas como autômatos. Através dos autômatos cientistas
da computação são capazes de compreender como máquinas
computam informações e resolvem problemas ou como uma
função pode ser definida como computável ou dedutível.
A teoria dos autômatos é o estudo de máquinas abstratas e
autômatas e como os problemas computacionais podem ser
mais bem resolvidos combinando o uso de diferentes tipos de
modelos computacionais, representa de forma finita uma
linguagem formal que pode ser um conjunto infinito [5].

.

II. TEORIA DOS AUTÔMATOS
A. Obejtivos
O objetivo maior da teoria dos autômatos é desenvolver
métodos pelos quais cientistas de computadores podem
descrever e analisar de forma dinâmica o comportamento de
sistemas discretos, nos quais sinais são periodicamente
exibidos. O comportamento desses sistemas discretos é
determinado pela maneira que o sistema é construído para
armazenamento e combinação de elementos. Algumas
características dessas máquinas incluem: entradas, saídas e
estados. Entradas podem ser definidas como sequências de
símbolos selecionadas de um conjunto / finito. A saber,
conjunto / é o conjunto de {x1, x2, x3… xk} onde k é o número
de entradas. Saídas são sequências de símbolos selecionadas de
um conjunto infinito Z. A saber, conjunto Z é o conjunto de
{y1, y2, y3… ym} onde m é o numero de saídas. E estados um
conjunto finito Q no qual a definição depende do tipo de
automação.

.

B. Principais Autômatos
Há quatro grandes famílias de autômatos:

  • Máquina de estado finito.
  • Autômatos de pilha.
  • Autômatos com memória linear.
  • Máquina de Turing.

As famílias de autômatos acima podem ser interpretadas de
uma forma hierárquica, onde a máquina de estado finito é o
autômato mais simples e a máquina de Turing o mais
complexo. Uma máquina de Turing é uma máquina de estado
finito ainda que o inverso não seja verdadeiro.

.
III. DEFINIÇÃO
Um autômato finito tem algumas partes descritas a seguir.
Ele tem um conjunto de estados e regras para ir de um estado a
outro, dependendo dos símbolos de entrada. Tem um alfabeto
de entrada que indica os símbolos permitidos. Tem um estado
inicial e um conjunto de estados aceitos. A definição formal diz
que um autômato finito é uma lista de cinco objetos: conjunto
de estados, alfabeto de entrada, regras de movimento, estado
inicial e estados aceitos. Em linguagem matemática essa lista é
frequentemente chamada de 5-tuple. Assim definimos
autômatos finitos como uma tupla contendo essas cinco partes.

.
A. Autômato Finito
Um autômato é representado formalmente por uma tupla
quíntupla (Q, Σ, δ, q
0, F), onde:

  • Q é um conjunto finito de estados.
  • Σ é um conjunto finito de símbolos, chamado de
    alfabeto do autômato.
  • δ é a função de transição, isto é, δ: Q x Σ → Q.
  • q0 é o estado inicial, 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 [3].

.

B. Autômato Finito Determinístico
Um autômato finito determinístico AFD ou máquina de
estados finita determinística é aquela que se encontra em um
único estado depois de ler uma sequência aleatória de entradas,
ou seja, para cada entrada existe somente um estado para o qual
o autômato pode se deslocar partindo do estado atual. Isso quer
dizer que a função de transição realiza o mapeamento de um
par composto por estado e símbolo para um único estado.
Deste modo cada palavra da entrada será sempre associada a
um único estado final como mostra a Fig.1.
autonomo_finito

Fig. 1. Exemplo de Autômato finito determinístico.
Um autômato finito determinístico pode ser definido
formalmente como uma tupla quíntupla (Q, Σ, δ, q0, F) onde:

  • Q é um conjunto finito de estados.
  • Σ um conjunto finito de símbolos de entrada chamado
    Alfabeto.
  • δ é uma função de transição δ: Q × Σ → Q.
  • q0 é um estado inicial onde q0 ∈ Q.
  • F é um conjunto de estados de aceitação (F ⊆ Q)

.

C. Autômato Finito Não-Determinístico
O não determinismo é um conceito útil que tem tido grande
impacto na teoria da computação [3]. Nem sempre a função de
transição de um autômato finito realiza o mapeamento de um
par composto por estado e símbolo para um único estado. Um
autômato finito não determinístico AFND é definido como uma
máquina de estados finita onde para cada entrada existem
diversos estados para os quais o autômato poderá se deslocar
partindo do estado atual. Possibilitando desse modo que cada
palavra de entrada possa ser associada a diversos estados finais.

autonomo_finito_ndetermin
Fig. 2. Exemplo de autômato finito não determinístico.

.
Um autômato finito não determinístico pode ser definido
formalmente como uma tupla quíntupla (Q, Σ, δ, q0, F) onde:

  • Q é um conjunto finito de estados.
  • Σ um conjunto finito de símbolos de entrada chamado Alfabeto.
  • δ é uma função de transição δ: Q × Σ → Q.
  • q0 é um conjunto de estados iniciais onde q0 ∈ Q.
  • F é um conjunto de estados de aceitação (F ⊆ Q) [3].

.

D. Equivalência entre autômatos finitos
Autômatos finitos determinísticos ou não determinísticos
reconhecem as mesmas classes de linguagens [1]. Um
autômato finito não determinístico pode ser transformado em
um autômato finito determinístico que aceita a mesma
linguagem mas o número de estados do AFD pode ser
exponencial com relação ao AFND. Todo o autômato finito
não determinístico tem um equivalente autômato finito
determinístico.

.
IV. EXEMPLO DE APLICAÇÃO
Como forma de exemplificar os estudos apresentados até
aqui, nas seções seguintes serão descritas as etapas da
modelagem de um sistema hipotético de caixa eletrônico. Por
simplificação a máquina modelada suprimiu alguns estados
existentes em sistemas de dispensação convencionais.

.
A. Alfabeto de entrada
Este conjunto de símbolos está associado a cada uma das
possíveis transições entre os estados existentes onde:
Σ= {cm, ck, si, ci, cs, sq, sa, ex, df, np, sf, rc, fi}
A tabela I descreve as transições correspondentes a cada um
dos símbolos deste conjunto.

.
tabela_i

.
B. Conjunto de estados possíveis
Este conjunto descreve os estados possíveis que a máquina
pode assumir à medida que o usuário realiza transações e é
definido como:
Q= {q0, q1, q2, q3, q4, q5, q6}
A tabela II descreve os estados para cada um dos símbolos
desse conjunto.
.

tabela_ii
C. Estágios passo a passo
Os estágios do autômato finito determinístico proposto para
solucionar o problema são descritos a seguir:
1) O estado q0 é o estado inicial e a máquina encontra-se
aguardando a ação do usuário, nesse estado é verificado se o
cartão está ok (ck) ou não (cm).
2) No estado q1 o usuário já inseriu o cartão e a máquina
aguarda a entrada correspondente a senha e conta corrente.
Se senha incorreta (si) ou conta incorreta (ci) o autômato
permanece nesse estado.
3) O próximo estado é o estado q2 neste ponto o usuário
deverá escolher a operação a ser realizada sendo elas: saldo
(sa), extrato (ex), saque (sq), ou encerrar a operação (fi).
Para cada ação o autômato avançará ao estado
correspondente, q3, q4, q5 ou q6 respectivamente.
4) O estado q3 exibe o saldo do cliente, se uma nova
operação (np) quer ser realizada ou autômato retorna ao
estado q2, se um saque (sq) vai ser realizado o autômato
avança para o estado q5 ou ainda finaliza a operação (fi) indo
ao estado q6.
5) O estado q4 aguarda a data para informar o extrato ao
cliente, a partir desse estado ele pode avançar ao estado q5
saque (sq), retornar ao estado q2, para uma nova operação
(np), permanecer nesse estado caso a data informada esteja
incorreta (df) ou avançar até o estado q6 finalizando (fi).
6) O estado q5 aguarda o valor para saque, caso valor esteja
fora dos limites (sf) ele continua nesse estado; retorna ao q2
para nova operação (np) ou avança para o estado final q6,
7) q6 é o estado final onde o cliente deve retirar o cartão (rc)
para finalizar a operação.

atm-system
Fig.3. Diagrama de transições do sistema.

.
CONCLUSÃO
Nesse artigo foram descritos os conceitos formais de
autômatos finitos determinísticos e não determinísticos e logo a
seguir foram abordadas as etapas de implementação de um
autômato finito determinístico para solucionar um problema
hipotético relacionado ao funcionamento de um sistema de
caixa eletrônico.

.
REFERÊNCIAS
[1] J. E. Hopcroft e J. D. Ullman, Introduction to Automata Theory,
Languages, and Computation, 1st ed. Vol. 1. Addison-Wesley
Publishing, Reading Massachusetts, 1979. (ver capítulo 2).
[2] K. II Culik,. Variations of the Firing-Squad Problem and Aplications. 3
rd
ed. Vol. 30 Information Processing Letters, 1989 pp. 153-157.
[3] M. Sipser, Introduction to the Theory of Computation, 1st ed. vol. 1.
Boston: PWS Publishing Company, 1997, pp. 33-61.
[4] A. S. Bonifácio e Y. Maldonado, “Modelagem de uma Vending
Machine utilizando um Autômato Finito com Saída,” não publicado.
[5] E. Roberts, “Automata Theory,” Sophomore College Class
http://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/refs.html (current Dec. 5, 2004).
[6] Jflap, Durhan, NC, Inglaterra. Duke University. (2009) [Online].
Disponível :http://www.jflap.org/, 2009, Accessado em: Sep. 01, 2015.

Anúncios
Esta entrada foi publicada em Artigos, Master e marcada com a tag , , , , , , . Adicione o link permanente aos seus favoritos.

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s