Autômato
Keywords: Autômato, Computador, Televisão, Teoria dos sistemas
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.
| Conteúdo |
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.
Autômato a pilha
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 1n01 + 1n, onde me n são inteiros não-negativos e an 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.
Autômatos Finitos Determinísticos
Um autômato de pilha é determinista se, qualquer que seja a combinação de estado, símbolo de entrada e topo da pilha, existe no máximo uma transição aplicável.