Autômato

Formalmente, um autômato ^{(português brasileiro)} ou autómato ^{(português europeu)} é definido como sendo um modelo matemático de uma máquina de estados finitos.

Um autômato funciona como um reconhecedor de uma determinada linguagem e serve para modelar uma máquina ou, se quiserem, um computador simples. É usado, por exemplo, em editores de texto para reconhecer padrões. Um conceito fundamental nos autômatos é o conceito de estado. Este conceito é aplicado a qualquer sistema, por exemplo, à nossa televisão. As noções de estado e sistema são tão onipresentes que foi desenvolvido um campo de conhecimento chamado Teoria dos sistemas. Uma televisão pode estar ligada(on) ou desligada(off), temos então um sistema com dois estados.

A um nível mais detalhado, podemos desejar diferenciar os canais, caso em que podemos ter centenas de estados: um para desligada e os restantes significando ligada no canal N, existe sempre um número finito de estados. Dada uma televisão, ela não está apenas num dos estados possíveis, somos capazes de fazer mudar a televisão de estado.

Autômatos finitos

São reconhecedores de linguagens regulares definidos através de quíntuplas da forma:

$M=(Q,\ \Sigma,\ \delta,\ q_{0},\ F)$

• $Q$ é um conjunto finito não vazio de estados do autômato;
• $\Sigma$ é um conjunto de símbolos, denominado alfabeto de entrada do autômato;
• $\delta:Q \times \Sigma \to Q$ é a função de transição de estados do autômato e seu papel é o de indicar as transições possíveis em cada configuração do autômato. Esta função fornece para cada par "estado e símbolo de entrada" um novo estado para onde o autômato deverá mover-se.
• $q_{0}\in\, Q$ é denominado estado inicial do autômato finito. É o estado para o qual o reconhecedor deve ser levado antes de iniciar suas atividades.
• $F\subseteq Q$ é um subconjunto do conjunto Q dos estados do autômato, e contém todos os estados de aceitação ou estados finais do autômato finito. Estes estados são aqueles em que o autômato deve terminar o reconhecimento das cadeias de entrada que pertencem à linguagem que o autômato define. Nenhuma outra cadeia deve ser capaz de levar o autômato a qualquer destes estados.

Por exemplo:
M = ({A, B}, {0, 1}, f, A, {B}) f = (A, 0) Þ A

(A, 1) Þ B

(B, 1) Þ B

(B, 0) Þ A

Para este autômato finito, reconhecem-se os seguintes elementos:

1. estados do autômato: A e B
2. símbolos do alfabeto de entrada: 0 e 1
3. estado final: B
4. estado inicial: A
5. linguagem reconhecida: cadeias de dígitos binários terminadas obrigatoriamente por um dígito 1.

Autômatos à pilha (ou pushdown)

São reconhecedores de Linguagens Livres de Contexto definidos através da sétupla da forma:

M=(E, V, P, f, q0, z0, F)
Onde:

• E é um conjunto finito não vazio de estados do autômato à pilha.
• V é um conjunto finito não vazio de símbolos de entrada ou átomos, denominado alfabeto de entrada do autômato à pilha. Os símbolos de entrada são os elementos de que são formadas as cadeias de entrada submetidas ao autômato para aceitação.
• P é um conjunto finito não vazio de símbolos da pilha, e forma o alfabeto da pilha. Os símbolos da pilha são os códigos armazenados pelo autômato em sua memória auxiliar. Esta memória, no caso do autômato à pilha, é organizada na forma de uma pilha, ou seja, os últimos dados armazenados são os primeiros a serem lidos da pilha, e vice-versa.
• f é a chamada função de transição do autômato à pilha, e é composta de um conjunto de produções que definem as regras de movimentação do autômato à pilha. Esta função mapeia o produto cartesiano E X (V É {l}) X P no produto cartesiano E X P*. Em palavras, dado um estado, um símbolo de entrada e um símbolo de pilha contido no topo da memória auxiliar, esta função determina um novo estado do autômato e o novo conteúdo do topo da pilha (de comprimento qualquer).
• q0 é denominado estado inicial do autômato à pilha, e é um elemento do conjunto E. É o estado em que se deve encontrar o autômato à pilha imediatamente antes do início do reconhecimento de uma cadeia de entrada (q0 Î E).
• z0 é um elemento do conjunto P, distinto dos demais pela convenção de que sua presença, no topo da pilha que implementa a memória do autômato, indica a ausência de outros elementos na mesma. É um marcador de pilha vazia (z0 Î P).
• F é um subconjunto do conjunto de estados E do autômato, que contém todos os chamados estados finais ou estados de aceitação do autômato de pilha. Tais estados correspondem àqueles nos quais o autômato de pilha deve encerrar o reconhecimento de todas as cadeias de entrada que sejam sentenças da linguagem definida pelo autômato à pilha. Nenhuma outra cadeia deve finalizar o autômato em qualquer destes estados.

Por exemplo:

M = ( { A, B, C}, {0, 1}, {x, y},

{ f(A, 1, y) Þ (A, yx),

f(A, 1, x) Þ (A, xx)

f(A, 0, y) Þ (B, y)

f(A, 0, x) Þ (B, x)

f(B, 0, x) Þ (B, x)

f(B, 1, xx) Þ (C, x)

f(B, 1, yx) Þ (C, y)

f(C, 1, xx) Þ (C, x)

f(C, 1, yx) Þ (C, y) },

A, y, {C} )

Este autômato reconhece cadeias binárias da forma $1^n0+1^n,$ onde $m$e $n$ são inteiros não-negativos e $a^n$ simboliza uma cadeia de $n$ símbolos $a$ seguidos.

Obs.: A cada transição, uma seqüência finita de símbolos de P é inserida na pilha, substituindo o símbolo do topo. Se a seqüência for l, equivale à ação "desempilhar". A inserção é tal que o símbolo mais à esquerda fica no topo da pilha.

Ver também

• Teoria de Autômatos
• Máquina de estado finito
• Planejamento Automatizado

Softwares

• Simulador de Autômatos - Software para criação, teste e conversão de Modelos Formais. Com interface gráfica.
• SCTMF - Software para Criação e Teste de Modelos Formais.
• JFlap - Software americano para testes com interface gráfica.

Referências

Autômatos finitos