Autômatos nitos e suas aplicações
Edgar Tomita
Josue Crispim
Autômatos finitos e suas aplicações
Resumo
Autômatos finitos são amplamente utilizados dentro da ciência da computação, a maior parte
dos compiladores e sistemas processadores de linguagem usam autômatos finitos. Não estando
restrito só a ciência da computação tem grande utilidade para a biologia e engenharia elétrica além
de sua grande importância no estudo de linguagens naturais. Os autômatos finitos estão divididos
em dois grupos os dos reconhecedores que são ser os determinı́sticos ou não determinı́sticos e os
transdutores que são ser as máquinas de Moore e Mealy. Eles reconhecem linguagens regulares ou
do tipo 3 segundo a hierarquia de Chomsky. Ao longo deste trabalho iremos revisar a teoria dos
autômatos, das máquinas reconhecedoras e transdutores, assim como uma abordagem prática do
uso dos autômatos finitos na bioinformática para a análise de sequências e para o uso em modelos
de predição e por último
1
Introdução
Autômato finito é uma abstração computacional que é usada amplamente em inúmeras áreas como
design de circuitos digitais para sistemas de modelagem, comunicação de protocolos, linguagens
de programação e design de compiladores. Processadores de texto freqüentemente usam autômatos
finitos é uma das ferramentas mais utilizadas na World Wide Web, na busca de uma ou um conjunto
de palavras.
Segundo [3] o termo ‘autômato finito’ descreve uma classe de modelos computacionais que são
caracterizados por terem um número finito de estados. Em particular os autômatos finitos formam
uma classe com linguagens restritas, devido essa restrição eles se tornam mais fáceis de serem
manipulados.
Divididos em dois grupos os das máquinas reconhecedoras que reconhecem a sua entrada e
usam seus estados para sinalizar o resultado para sinalizar o resultado para o mundo externo. E os
transdutores que geram uma saı́da baseada em uma entrada ou estado utilizando ações. Amplamente
utilizado para aplicações de controle. Dentro dos transdutores temos as máquinas de Moore e Mealy.
Iremos estudar a teoria dos autômatos finitos em 2, então entraremos em detalhes, nos grupos que
formam os autômatos finitos primeiramente com os reconhecedores estudando os autômatos finitos
determinı́sticos em 3 e então os autômatos finitos não determinı́sticos em 4 assim como algumas
operações nesse grupo.
Em 8 iremos estudar a teoria por traz transdutores, as máquinas de Moore e Mealy, assim como
algumas operações realizadas nesse grupo.
Também iremos ver em 9 a aplicação do que foi estudado, para algumas tarefas na manipulação
de dados e modelos de predição utilizados na bioinformática como comparação de sequências 5.1,
detecção de padrões dentro da sequência 5.2 e Detecção de regiões reguladoras no gene 5.3. e
finalizando em 10 a aplicação de autômotos em jogos.
2
Autômatos finitos
Em considerações gerais os reconhecedores são sistemas em que eles tem como entrada uma palavra
α ∈ Σ, será lido sı́mbolo por sı́mbolo até o final da palavra, caso não encontre erros antes, e no
último sı́mbolo da palavra o autômato estiver no estado de aceitação, a palavra é aceita, o oposto ela
é rejeitada. Os reconhecedores contêm um conjunto de estados finitos e o seu “controle” se desloca
para outro estado de acordo com a “entrada” externa.
Exemplo 1. Autômato reconhecedor simples.
Um interruptor liga/desliga que memoriza o estado “ligado” e “desligado”, e permite que o
usuário mude de estado diferente do que está através de um botão. Se o interruptor estiver no
estado ”ligado”, após pressionar o botão levará o estado para “desligado”, se estiver no ”desligado”,
e pressionar o botão irá para o ”ligado”.[2]
Figura 1: A figura 1 apresenta o autômato finito para o interruptor. Os estados são apresentados pelos cı́rculos
(ligado e desligado) e os arcos apresentam as “entradas”, representado as influências externas (pressionar). A idéia é
de que o sistema mude de estado toda vez que a entrada pressionar é recebida.
O estado “inicial” em um autômato é indicado pela seta inı́cio. Muitas vezes é necessário indicar
um ou mais estados como sendo “finais” ou de “aceitação”. Este estado é indicado por um cı́rculo
duplo.
Uma das formas de representação de um autômato é de diagrama de estado de transição ou
grafo. Que é um grafo orientado onde os nos são os estados e as arestas nomeadas com os sı́mbolos
representam a mudança de estado ou transição causada pela leitura do terminal segundo[7].
Exemplo 2. Constantes Decimais.[7]
L o conjunto de decimais constantes tem o alfabeto Σ = ∆ ∪ {0,•} onde delta = 0,1,2,3,4,5,6,7,8,9
é um digito diferente de 0.
Dado uma palavra 0 • 2 •, o autômato anda pelos estados q0 , q2 , q3 , q4 . No último estado, uma
vez que nenhuma transição permita a leitura de um simbolo a •, o cálculo pára antes da palavra
seja lida por inteiro. Como uma consequência, a palavra não é aceita. Por outro lado, a entrada 0
• 21 seria ser aceita.
Se quisermos modificar a linguagem para as contantes 305 • terminando com um decimal o e
um ponto serem aceitas, o q3 também tem que ser marcado como estado final [7].
2
Figura 2: Diagrama de estado ou grafo (esquerda) e tabela (direita) para constantes decimais
(exemplo 1)
3
Autômatos finitos determinı́sticos
Quando o autômato não pode estar em mais de um estado em qualquer momento, se diz que é
determinı́stico1 . Pode ser definido simplesmente por AFD ou DFA.
O autômato finito determinı́stico é uma 5-upla onde:
1. Σ representa um conjunto finito de sı́mbolos de entrada;
2. Q conjunto de estados possı́veis do autômato;
3. δ função de transição;
4. q0 estado inicial;
5. F conjunto de estados finais.
Assim, temos uma “tupla de cinco elementos”:
A = (Σ, Q, δ, q0 , F )
Todo autômato finito tem pelo menos um estado, que é o estado inicial q0 . Os sı́mbolos de
entrada são representados pelo alfabeto Σ e a função de transição δ especifica o movimento, por
exemplo quando aparece δ(q, a) = r, significa que a maquina M que está no estado q lê a e vai para
r caso δ(q, a) é indefinido o autômato para.
O autômato processa uma palavra não vazia x com uma serie de movimentos. Pegando x = ab,
lendo o primeiro caractere, o primeiro passo δ(q0 , a) = q1 leva ao estado q1, então para o q2 pelo
segundo passo δ(q1 , b) = q1 . Podemos também escrever de forma reduzida δ(q0 , ab) = q2 que diz
lendo a palavra ab a maquina move para o estado q2 .[7]
Um caso especial e a palavra vazia. Que não assume mudanças de estado:
1
O termo “determinı́stico” se refere ao fato de que, para cada entrada, existe um e somente um estado ao qual o
autômato pode transitar a partir de seu estado.[2]
3
∀q ∈ Q : δ(q, ε) = q
Seguindo temos que o domı́nio da função transição é QΣ∗ e a definição é:
δ(q, ya) = δ(δ(q, y), a), onde a ∈ Σ e y ∈ Σ∗
Olhando o autômato como grafo, se δ(q, y) = q 0 , então, e somente então, existe um caminho do
no q para o no q 0 , tal que a concatenação das arestas tem as palavra y. Dizemos que y é um rotulo
do caminho.
A palavra x e reconhecida ou aceita por um autômato se é um rotulo de um caminho do estado
inicial até o estado final, δ(q0 , x) ∈ F .
A linguagem reconhecida ou aceita pelo autômato M é:
L(M ) = x ∈ Σ∗{x e reconhecida por M }
Dois autômatos são equivalente se eles aceitam a mesmo linguagem.
O autômato processa uma palavra não vazia com uma série de movimentos e pode ser visto como
sendo uma máquina composta por três partes:[4]
1. Fita: contém a informação a ser lida;
2. Unidade de Controle: reflete o estado da máquina. A unidade de leitura acessa uma célula da
fita de cada vez. Sempre da esquerda para a direita
3. Função de transição ou Programa: comanda as leituras definindo o estado da máquina.
A fita é dividida em célula e é finita. Cada célula armazena um sı́mbolo que pertencem a entrada.
Não existe nenhuma memória auxiliar e também não é possı́vel gravar sobre a fita. A informação a
ser coletada ocupa toda a fita.
Na unidade de controle, os estados são predefinidos e em um número finito. O sı́mbolo é lido
uma célula de cada vez. Depois de lido a unidade de controle é deslocada para a direita a fim de ler
o próximo sı́mbolo, assim sucessivamente até o fim da fita.
Figura 3: Fita representando um autômato finito.
O programa define o novo estado do autômato após a leitura. Como não há nenhuma memória
auxiliar, utiliza-se o conceito de estado para armazenar as informações.
4
3.1
Função programa estendida
Dado δ(q, ya) = δ(δ(q, y), a), um DFA, em [4] a função programa estendida é definida por:
δ : Q ΣßQ
é a função programa : QΣßQestendida para palavra, definida por indução:
δ(q, ε) = q
δ(q, wa) = δ(δ(q, a), w)
3.2
Autômatos vacuosos
Se o conjunto de estados finais dos autômatos for vazio a linguagem gerada também é vazia, ou seja,
L = 0.Mas existem AFDS com estados finais que geram a linguagem vazia, para acontecer isso não
poderá existir nenhum caminho que comece no estado inicial e termine no estado final. Todo AFD
que a linguagem for vazia é designado por AFD vacuoso.
3.3
Estados acessı́veis, produtı́veis e inúteis
Em um autômato um estado e acessı́vel se ele começa no estado inicial q0 e termina em um estado
q. Um estado q é produtivo se existe um caminho entre ele e o estado final. Um estado q é inútil se
ele não for acessı́vel e não for produtivo.
4
Autômatos Finitos Não-Determinı́sticos
O autômato finito não-determinı́stico, ou simplesmente NFA ou AFND, pode estar em vários estados
ao mesmo tempo com isso fica mais fácil a leitura do grafo do autômato e também permite definições
mais curtas. Diferente da AFD, a função de transição da NFA não define necessariamente o próximo
estado, porém fornece uma lista de estado para as quais a transição poderia ser feita. A lista tem
um número ≥ 0.
Enquanto a NFA aceita uma cadeia se o último estado atingido é final, na NFA a cadeia é aceita
se existe uma sequência de escolhas onde o último estado atingido é final.
O autômato finito não-determinı́stico é uma 5-upla onde:
1. Σ representa um conjunto finito de sı́mbolos de entrada;
2. Q conjunto finito de estados;
3. δ função de transição. Recebe um estado Q e um sı́mbolo do alfabeto e retorna um F. No
NFA é um conjunto de estados enquanto que no NFA é um único estado;
4. q0 estado inicial;
5. F conjunto (subconjunto de Q) de estados finais.
Assim, temos uma “tupla de cinco elementos”:
A = (Σ, Q, δ, q0 , F )
Exemplo 3 [7]
Seja a cadeia de entrada ababa e a NFA dado pelo diagrama da figura:
5
Figura 4: Diagrama que representa o autômato finito não-determinı́stico
A cadeia é aceita, pela sequência de estados q0 , q1 , q1 , q1 , q1 , q2. A sequência de estado poderia
ser também q0 , q1 , q1 , q1 , q1 , q1 que não leva a um estado final. Há uma sequência que é interrompida,
q0 , q1 , q1 , q2 , que não prevê uma transição com o segundo b. Mesmo com esses casos o autômato é
aceito, porque há um caminho certo.
Este afnd aceita a linguagem das cadeias (de comprimento maior ou igual a 2), cujo primeiro
e último sı́mbolos são a, sendo os restantes quaisquer. (Compare este afnd com o afd de um dos
exemplos anteriores, que aceita a mesma linguagem.)
Temos, para a mesma cadeia ababa de entrada,
(q0, ababa) ` (q1, baba) ` (q1, aba) ` (q1, ba) ` (q1, a) ` (q2, e)
e, portanto, ababa I L(M). Temos também o ”caminho errado”
(q0, ababa) ` (q1, baba) ` (q1, aba) ` (q1, ba) ` (q1, a) `(q1, e)
que leva à configuração não final (q1, e), e não permite nenhuma conclusão.
Cadeias como bab e abab não levam a configurações finais e não são aceitas. Da
configuração (q0, bab) nenhuma configuração é atingı́vel; para abab temos:
(q0, abab) ` (q1, bab) ` (q1, ab) ` (q1, b) ` (q1, e)
Adicionalmente, temos um outro caminho
(q0, abab) ` (q1, bab) ` (q1, ab) ` (q2, b)
que também não atinge nenhuma configuração final. Assim, as cadeias bab e abab não
são aceitas e não fazem parte de L(M).
Exemplo 4 [7]
Considere o afnd M da Fig. 4.5. M aceita cadeias da forma c y c, onde c pode ser a ou b e y
pode ser qualquer cadeia de a’s e b’s. A cadeia ababa = cÖyÖc = aÖbabÖa é aceita por M, através
da sequência de configurações abaixo, em que a primeira e a última transições são realizadas através
de transições-e.
(A, ababa) M lê e e adivinha que c=a
` (B, ababa) M lê a e confere que c=a
` (C, baba) M lê b
` (C, aba) M lê a e adivinha que este a faz parte de y
` (C, ba) M lê b
6
` (C, a) M lê a e adivinha que este a é o último c
` (D, e) M lê e e adivinha que a cadeia acabou
` (I, e) M aceita
Figura 5: AFND para o exemplo
Todas as configurações atingı́veis (caminhos certos e errados) estão indicadas abaixo:
(A, ababa)
` (B, ababa)
. ` (C, baba)
. ` (C, aba)
. ` (C, ba)
. . ` (C, a)
. . ` (C, e) – não aceita
. . ` (D, e)
. . ` (I, e) – ok! aceita!
. ` (D, ba)
. ` (I, ba) – bloqueado
` (F, ababa) – bloqueado
4.1
Função programa estendida
Dado A = (Σ, Q, δ, q0 , F ), um NFA, em [4] a função programa estendida é definida por: δ : 2Q
Σ ß 2Q é a função programa δ : Q Σ ß 2Q estendida para palavra e por indução definida como:
δ (P, ε) = P
δ (q, aw) = δ(∪ q ε P δ (q, a), w)
Assim, para um dado conjunto de estados (q1 , q2 ...qn ) e para um dado sı́mbolo a:
δ({q1 , q2 ...qn }, a) = δ (q1 , a) u δ(q2 , a)u...uδ(qn , a)
A linguagem aceita por NFA M, denotada por ACEITA(M) ou L(M), é o conjunto de todas as
palavras pertencentes a Σ tais que existe um caminho alternativo que aceita ou rejeita a palavra,
ou seja:
7
ACEITA(M) = { w — existe q ε δ(qn , w) tal que q F}
REJEITA(M), é o conjunto das palavras pertencentes a Σ rejeitadas por todos os caminhos
alternativos de M, a partir de q0 ).
5
Equivalência entre AFD e AFN
Há uma equivalência entre as duas classes de autômatos: os determinı́sticos e não-determinı́sticos.
Prova:
A ideia é mostrar que a partir de um AFN M qualquer, é possı́vel construir um AFD A0 . O
algoritmo demonstra a conversão de um AFN qualquer em um AFD equivalente. O objetivo é a
construção de estados de A0 tal que simule as diversas combinações de estados alternativos de M.[4]
Seja A0 = (Σ, Q, δ, q0 , F ) um AFN qualquer e A0 = (Σ, Q’, δ’, <q0 >, F’ ) um AFD construı́do
a parti de A:
1. A’: todas as combinações possı́veis, sem repetições, de estados de Q as quais são denotados
por < q1 q2 ....qn > sendo que qi pertence a Q e i = 1. A ordem dos elementos não distingue
mais combinações, ou seja, < qu qv >=< qv qu >;
2. δ’: tal que δ’(< q1 ....qn >, a) =< p1 ....pn >se, e somente se, δ({q1 ....qn }, a) = ({p1 ....pm } Ou
seja, a imagem de todos os caminhos alternativos de A é representado por M 0 ;
3. F: conjunto de estados < q1 q2 ....qn > pertences a Q0 tal que alguma componente qi pertence
a F, i > 1.
A demonstração de que A0 simula o processamento de A é por indução da tamanho da palavra.
Supondo que w é uma palavra qualquer de Σ, deve-se mostrar que:
δ’(< q0 >, w) = < q1 ....qu > se, e somente se, δ’(q0 , w) = q1 ....qu
1. Base de indução.Seja w tal que — w — = 0. Então:δ’(< q0 >, ) = < q0 >se, e somente se
δ’(q0 , ) = q0
2. Hipótese de indução.Seja um w tal que — w — = n e n > 1 Suponha verdadeiro que: δ’(< q0 >,
w) = < q1 ....qu > se, e somente se δ(q0 , w) = < q1 ....qu >
3. Passo de indução.Seja um w tal que — wa — = n + 1 e n > 1 Suponha verdadeiro que:
δ’(< q0 >, w) = < p1 ....pu >se, e somente se δ(q0 , w) = p1....pu o que equivale: δ’(< q0 >,
w) = < p1 ....pv > se, e somente se δ’({q1 ....qu }, w) = < p1....pu > o que é verdadeiro, por
definição de δ’.
Portanto, A’ simula A para qualquer w pertencente a Σ.
6
Autômato Finito com Movimentos Vazios
Trata-se de uma generalização dos modelos de máquinas não-determinı́sticas. Uma transição sem
leitura de um sı́mbolo na fita caracteriza o movimento vazio. Uma das vantagens, está no fato de
facilitar demonstrações e construções relacionados a autômatos.
Em autômatos Finitos, a facilidade de movimentos vazios não melhora o reconhecimento de
linguagens. Qualquer Autômato Finito com Movimentos Vazios pode ser simulado por um Autômato
Finito Não-Determinı́stico.
8
O autômato finito não-determinı́stico com movimentos vazios, conhecido como AFN ou AF é
uma 5-upla, onde:
1. Σ representa um conjunto finito de sı́mbolos de entrada;
2. Q conjunto finito de estados possiveis;
3. δ função de transição D:Q(Σ ∪ { }ß2Q
4. q0 estado inicial;
5. F conjunto (subconjunto de Q) de estados finais.
Assim, temos uma “tupla de cinco elementos”:
A = (Σ, Q, δ, q0 , F )
7
Minimização de autômatos
A ideia da minimização de autômatos, é gerar um autômato finito equivalente com o menor número
de estados possı́veis. Entretanto, a minimização não garante um custo menor na implementação.
O autômato minimizado, chamado de Autômato Finito Mı́nimo, é único a menos que seja um
isomorfismo. Por exemplo, se dois autômatos aceitam uma linguagem, ao serem minimizados terão
o mesmo Autômato Finito Mı́nimo
A definição de um Autônomo Mı́nimo é descrito por como: Uma linguagem regular L é AFD,A
= (Σ, Q, δ, q0 , F ) tal que ACEIT A(M ) = L e que para qualquer outro AFD A0 = (Σ, Q, δ, q0 , F
), tal que ACEITA(M) = L, tem-se que #Q03 #Q.[4]
Para minimizar um autômato deve-se respeitar:
1. O Autômato é determinı́stico;
2. Não possui estados inacessı́veis;
3. Função programa total. São previstas transições para todos os sı́mbolos do alfabeto a partir
de qualquer estado.
Caso algum desses casos não seja satisfeita não é possı́vel realizar a minimização a menos que
os problemas sejam corrigidos.
O algoritmo proposto por [1] é descrito como: A partir de um AFD, A = (Σ, Q, δ, q0 , F ) que
satisfaz todas as regras para minimização de um autômato. Os passos para do algoritmo são os
seguintes:
1. Tabela. Relacionar os estados distintos através de uma tabela, onde cada par de estados ocorre
somente uma vez, como na figura:
9
Figura 6: tabela com os estados minimizados
2. Marcação dos estados trivialmente não-equivalentes. Marcar os pares do tipo estado final,
estado não-final. Estados finais não são equivalentes aos estados não-finais.
3. Marcação dos estados não equivalentes. Para cada sı́mbolo a pertencente ao alfabeto e para
cada par (qu , a), suponha que δ(qu , a) = pu e δ(qv , a) = pv e:
(a) Se pu = pv , então ambas são equivalentes para o sı́mbolo a e não deve ser marcado;
(b) Se pu 6= pv e o par {pu , pv } não está marcado, então inclui-se {qu , qv } é incluso em uma
lista a partir de {pu , pv } para análise;
(c) Se pu 6= pv e o par {pu , pv } está marcado, então:
i. {qu , qv } não é equivalente, portanto é marcado;
ii. se {qu , qv } encabeça uma lista de pares, marcar todos os pares da lista e recusivamente, se algum par da lista encabeça outra lista;
4. Unificação dos estados equivalentes. Podem ser unificados os estados dos pares não marcados
da seguinte maneira:
(a) são unificados em um único estado não-final os pares de estados não-finais equivalentes;
(b) são unificados em um único estado final os pares de estados finais equivalentes;
(c) o estado unificado é inicial se alguns dos estados equivalentes é inicial;
5. Exclusão dos estados inúteis. São excluı́dos os estados inúteis. Um estado q é inútil se é
não-final e não se atinge ao estado final através dele.
10
Figura 7: Autômato Finito a ser minimizado
8
Máquinas de Moore e de Mealy
A Máquina de Moore possui uma função que gera uma palavra de saı́da (que pode ser vazia) para
cada estado da máquina. Esta saı́da só depende do estado atual da máquina.
Já a Máquina de Mealy é um Autômato Finito modificado de forma a gerar uma palavra de
saı́da para cada transição entre os estados. Neste tipo de máquina de estados estas palavras de
saı́da dependem do estado atual e do valor das entradas.
Definições formais:
Uma Máquina de Mealy M é autômato finito determinı́stico com saı́das associadas às transições
e pode ser representada formalmente pela sêxtupla M = (Σ, Q, δ, q0 , F , ∆), onde: [8]
1. Σ é um alfabeto de sı́mbolos de entrada.
2. Q é um conjunto de estados possı́veis do autômato, o qual é finito.
3. δ é a função programa ou de transição
4. q0 é o estado inicial do autômato,tal que q0 é elemento de Q
5. F é um conjunto de estados finais tal que F está contido em Q.
6. ∆ é um alfabeto de sı́mbolos de saı́da.
O processamento de uma Máquina de Mealy para uma dada entrada w consiste na aplicação
sucessiva da função programa para cada sı́mbolo de w (da esquerda para a direita), até ocorrer uma
condição de parada. Caso a saı́da da função programa seja uma palavra vazia, nenhuma gravação é
realizada, ou seja, a cabeça da fita não se move. Porém se todas as transições de uma determinada
máquina de Mealy gerarem saı́das vazias, então esta se comporta como um Autômato Finito.
Já uma Máquina de Moore M, como dito anteriormente, é um Autômato Finito Determinı́stico
com suas saı́das associadas aos estados. É representada formalmente por uma septupla M = (Σ, Q,
δ, q0 , F , ∆, δS), onde:[8]
1. Σ é um alfabeto de sı́mbolos de entrada.
11
2. Q é um conjunto de estados possı́veis do autômato, o qual é finito.
3. δ é a função programa ou de transição
4. q0 é o estado inicial do autômato,tal que q0 é elemento de Q
5. F é um conjunto de estados finais tal que F está contido em Q.
6. ∆ é um alfabeto de sı́mbolos de saı́da.
7. δS é a função de saı́da a qual é uma função total.
O processamento de uma Máquina de Moore ocorre da mesma forma que na máquina de Mealy,
assim como o tratamento de saı́das vazias. Assim como a Máquina de Mealy, se todos os seus estados
gerarem saı́da vazia, ela também se comporta como um Autômato Finito.
8.1
8.1.1
Exemplos
Máquina de Mealy
Uma aplicação comum e freqüentemente recomendada para os autômatos com saı́da é o projeto de
diálogo entre um programa (de computador) e o seu usuário. Neste caso, o diálogo poderia se dar
de duas maneiras: ser comandado pelo programa ou pelo usuário.
8.1.2
Máquina de Moore
Um exemplo comum de aplicação do conceito de Máquina de Moore é o desenvolvimento de Analisadores Léxicos de compiladores ou tradutores de linguagens em geral. Basicamente, um analisador
léxico é um Autômato Finito (em geral, determinı́stico) que identifica os componentes básicos da
linguagem como, por exemplo, números, identificadores, separadores, etc. Uma Máquina de Moore
como um Analisador Léxico é como segue:
1. um estado final é associado a cada unidade léxica;
2. cada estado final possui uma saı́da (definida pela Função de Saı́da) que descreve ou codifica a
unidade léxica identificada;
3. para os demais estados (não- finais) a saı́da gerada é a palavra vazia.
8.2
Equivalência entre máquinas de Mealy e Moore
A equivalência dos dois modelos de Autômato Finito com Saı́da não é válida para a entrada vazia.
Neste caso, enquanto a Máquina de Moore gera a palavra correspondente ao estado inicial, a Máquina
de Mealy não gera qualquer saı́da, pois não executa transição alguma. Entretanto, para os demais
casos, a equivalência pode ser facilmente mostrada. Assim, toda Máquina de Moore pode ser
simulada por uma Máquina de Mealy, para entradas não vazias, e Toda Máquina de Mealy pode
ser simulada por uma Máquina de Moore. No caso de saı́das vazias, o que ocorre é que enquanto a
Máquina de Moore gera a palavra correspondente ao estado inicial, a Máquina de Mealy não gera
qualquer saı́da, pois não executa transição alguma, tornando assim as duas incompatı́veis.
12
9
Aplicação dos autômatos finitos na bioinformática
A teoria dos autômatos finitos tem grande utilidade na bioinformática, muitos problemas como
análise, processamento, simulação e interpretação dedados biológicos podem ser associados com os
autômatos. Como um exemplo, na detecção de padrões nas sequências de DNA e aminoácidos.
Outro uso comum para a bioinformatica é na comparação de saı́das de sequências, assim como
simulações e predições. Todas essas aplicações requerem algoritmos e/ou autômato.
9.1
9.1.1
Problemas especifı́cos
Comparação de sequências
No DNA e aminoácidos há certos padrões em partes da sequencia que são de grande interesse para a
bioinformática. Há também o interesse na comparação da sequencia inteira que geralmente é muito
grande e ver quais transformações a sequência tem. Isso é relevante porque duas ou mais sequencias
podem serem equivalentes sem serem idênticas. Inserções, deleções e rearranjo de nucleotı́deos e
aminoácidos, por exemplo, podem ocorrer. Essas transformações nas sequencias são possı́veis e
podem ocorrer naturalmente. [5]
Esses problemas são diretamente aplicados a certas áreas da teoria dos autômatos. A teoria
dos autômatos pode ser generalizada e aplicada para discernir quais algoritmos podem ser criados e
quais não podem. Também pode ser usada para considerações sobre tem e espaço. Isto é relevante
devido a “urgente necessidade de desenvolvimento de algoritmos” para a comparação de sequências
[5].
9.1.2
Detecção de padrões dentro das sequências
O reconhecimento de padrões pode ser determinado pelo mecanismo dos autômatos porque é comparado pequenas partes da sequência ou subsequências dentro da sequencia. Mas há uma grande
complexidade em fazer isso devido à ambiguidade e o não determinismo constantes na biologia. [5]
Nesse artigo, Cohen da um exemplo de gramática que poderia ser feita para descrever a sintaxe
de genes. Ele apresenta a idéia de representar um gene como um não terminal nessa gramática,
mas ao mesmo tempo admite que isso pode ser uma tarefa muito difı́cil. Também uma gramática
livre de contexto pode ser implementada para mapear as sequências de RNA em uma estrutura
bidimensional e que pode ser transformado em um autômato finito para definir a mesma linguagem.
9.1.3
Detecção de regiões reguladoras de genes
No cálculo para a predição das regiões reguladoras dos genes, padrões que tem significante sobre ou
sub-representação dentro do genoma ou das proteı́nas são grandes candidatos para serem elementos
que ajudam na expressão ou repressão de gene, também conhecidos como elementos reguladores.
Com os autômatos finitos, é possı́vel achar uma solução para o problema não só para achar as regiões
reguladoras trabalhando em conjunto com cadeias de Markov, mas também para o tratamento
estatı́stico. (PaoloRibeca andEmanueleRaineri) [6]
10
Aplicação de Autômatos em Jogos
Na área da informática sempre houve um desejo que o computador se interagisse mais com o ser
humano, jogando e aprendendo com seu erros para que aumente seu desempenho. É nessa área que
13
entra a Inteligência Artificial (IA), que nos últimos anos tem se desenvolvido bem criando programas
cada vez mais humanos, atuando e tomando decisões.
No ramo dos jogos, as técnicas de IA estão bem desenvolvidas com jogos mais inteligentes e
realistas. O destaque fica por conta dos Jogos de Tiro em Primeira Pessoa ou FPS (First Person
Shooter). Neste, o jogador controla o personagem como se ele próprio estivesse ali, com a visão de
primeira pessoa e armas para cumprir diversos tipos de missões. É nesses jogos em que os autômatos
finitos entram em cena.
Um exemplo de autômato finito em um jogo de FPS é o Quake. Quando lançado, o seu código
foi autorizado para ser usados por outras companhias que produziram grandes jogos provando o
sucesso da técnica. [1]
A Figura 8 mostra o autômato de um foguete Quake, um projétil de uma arma chamada Rocket
Launcher, operada e possuı́da por um jogador. A figura é bem próxima de um Diagrama de Transição
de Estado. As caixas numeradas por 1 representam os estados, 2 são os gatilhos e as setas são
transições de estado e 3 são os pontos de entrada e saı́da.
Figura 8: Representação de transição de estado do projétil de foguete
O diagrama representa o ciclo de vida do projétil. O [1] faz uma interpretação subjetiva do
código afirmando que o projétil é criado como sendo o produto de uma ação com outro autômato,
chamada de Rocket Launcher em sua Ação de Tiro. Quando a instância do projeto desaparece, ela
é excluı́da do jogo.
Quake faz um extenso uso de autômatos finitos que controlam os agentes que existem no ambiente
do jogo.
11
Conclusão
Com certeza, na área de Computação, a teoria de autômatos é uma ferramenta fundamental a ser
compreendida. É a base de toda a linguagem e na construção de um compilador. Além disso, é
empregada em outras áreas como na bioinformática e em circuitos de sistemas digitais.
Os games também ganharam a sua contribuição, em especial nos Jogos de Tiro em Primeira
Pessoa. Possibilitando assim, uma interação maior entre o jogador e o jogo.
Basicamente os autômatos finitos são determinı́sticos (DFA) ou não-determinı́sticos (NFA). No
DFA, o autômato não pode estar em mais de um estado em certo momento, enquanto no NFA pode.
14
Ambas são 5-tuplas com a diferença no seu retorno. NFA retorna um conjunto de estado e DFA
retorna um único estado.
Outra classificação de autômatos finitos são os Autômatos Finitos com Movimentos Vazios. O
principal aspecto está de que nesse autômato é permitida a transição para uma entrada vazia, sem
sı́mbolo de entrada.
É possı́vel também de se chegar em DFA a partir de um NFA que aceite a mesma linguagem.
A minimização de autômatos finitos, mesmo não diminuindo o custo na implementação, é uma
grande aliada para representar um mesmo autômato finito com um menor número de estados.
Para tal é necessário respeitar três regras: ser determinı́stico, não possuir estados inacessı́veis e ser
previstas transições para todos os sı́mbolos do alfabeto a partir de qualquer estado.
Referências
[1] M.A.C.Simôes C.S. Dinizio. Inteligência artificial em jogos de tiro em primeiro pessoa. 2002.
[2] R.Motwani j.E. Hopcroft, J.D.Ullman. Introdução à Teoria de Autômatos, Linguagens e Computação. Elsevier Editora Ltda, Rio de janeiro, 2003.
[3] M. V. Lawson. Finite automata. Heriot-Watt University, Scotland, 2004.
[4] Paulo Fernando Blauth Menezes. Linguagens Formais e Autômatos. Sagra Luzzato, Porto
Alegre, RS, 1998.
[5] R.P. Nakamoto. An insight into automata theory and bioinformatics. 2006.
[6] E.Raineri P.Ribeca. Faster exact markovian probability functions for motif occurrences : a
dfa-only approach. bioinformatics, 24:2839–2848, 2006.
[7] S. C. Reghizzi. Formal Languages and Compilation. Springer, London, 2009.
[8] Henrique Eduardo M. de Oliveira Roberta C. de Brito, Diogo M. Martendal. Máquinas de
estados finitos de mealy e moore. 2003.
15