Autômato

Origem: Wikipédia, a enciclopédia livre.

Formalmente, um autômato é 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.

[editar] Autômatos finitos

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

M=(E,V,f,q0,F)

E é um conjunto finito não vazio de estados do autômato finito.
V é denominado alfabeto de entrada do autômato e corresponde a um conjunto finito não vazio dos símbolos de entrada ou átomos indivisíveis que compõem a cadeia de entrada submetida ao autômato para aceitação.
f é uma função de transição de estados do autômato e seu papel é o de indicar as transduções possíveis em cada configuração do autômato. Esta função mapeia o produto cartesiano E X (V È {l}) em E, ou seja, fornece para cada par (estado, símbolo de entrada) um novo estado para onde o autômato deverá mover-se.
q0 é denominado estado inicial do autômato finito, e corresponde a um elemento do conjunto E. É o estado para o qual o reconhecedor deve ser levado antes de iniciar suas atividades (q0 Î V).
F é um subconjunto do conjunto E 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 (F Í V).

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:

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

[editar] 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 n 01 + 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.

[editar] Ver também

Teoria de Autômatos: Linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Estrutura de frase	Recursivamente enumerável	Máquina de Turing
--	Estrutura de frase	Recursiva	Máquina de Turing
Tipo-1	Sensíveis ao contexto	Sensíveis ao contexto	Máquina de Turing com memória limitada
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito