Autômato – Wikipédia a enciclopédia livre

Prévia do material em texto

Autômato
Origem: Wikipédia, a enciclopédia livre.
Formalmente, um autômato ou 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.
Índice
1 Autômatos finitos
2 Autômatos à pilha (ou pushdown)
3 Ver também
4 Softwares
5 Referências
Autômatos finitos
São reconhecedores de linguagens regulares definidos através de quíntuplas da forma:
 é um conjunto finito não vazio de estados do autômato;
 é um conjunto de símbolos, denominado alfabeto de entrada do autômato;
 é 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.
 é denominado estado inicial do autômato finito. É o estado para o qual o reconhecedor deve
ser levado antes de iniciar suas atividades.
 é 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.
(português brasileiro) (português europeu)
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 onde e são inteiros não-negativos e 
simboliza uma cadeia de símbolos 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
Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito
Softwares
Simulador de Autômatos (http://www.simuladordeautomatos.com) - Software para criação, teste e
conversão de Modelos Formais. Com interface gráfica.
SCTMF (http://www.din.uem.br/yandre/sctmf/) - Software para Criação e Teste de Modelos Formais.
JFlap (http://www.jflap.org) - Software americano para testes com interface gráfica.
Referências
Autômatos finitos (http://www.dca.fee.unicamp.br/cursos/EA876/apostila/HTML/node46.html)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Autômato&oldid=32044915"
Categorias: Palavras que diferem em versões da língua portuguesa Teoria dos autômatos
Teoria da computação Matemática discreta Ciência da computação
Esta página foi modificada pela última vez à(s) 09h35min de 31 de agosto de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.