Autômatos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1037 palavras )
  • Download(s) : 0
  • Publicado : 28 de agosto de 2012
Ler documento completo
Amostra do texto
Autômatos Finitos

Autômato finito é um modelo matemático usado para representar programas de computador ou circuitos lógicos. O conceito é concebido como uma máquina abstrata que deve estar em um de seus finitos estados. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde aentrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.
São procedimentos aceitadores, ou reconhecedores, pode conter uma quantidade finita e limitada de informação. Essainformação é representada por um estado da máquina, e só existe um número finito de estados. Essa restrição faz com que o autômato finito seja severamente limitado na classe de linguagens que são reconhecidas.

Máquinas de estado finito podem modelar um grande número de problemas, entre os quais a automação de design eletrônico, projeto de protocolo de comunicação, análise e outras aplicações deengenharia. Na biologia e na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, utilizadas para descrever sistemas neurológicos e em lingüístico para descrever as gramáticas das linguagens naturais.

Não determinístico
A função de transição de um autômato finito não determinístico não precisa determinar exatamente qual deve ser o próximoestado. Em vez disso, a função de transição fornece uma lista (um conjunto) de estados para os quais a transição poderia ser feita. Essa lista pode ser vazia, ou ter um número qualquer positivo de elementos. Essa possibilidade de escolha entre vários caminhos a serem seguidos nos leva a modificar a definição de aceitação. Um afd aceita se "o último estado atingido é final";
Mas um afnd aceita umasequência de escolhas tal que o último estado atingido é final". Podemos alternativamente imaginar que o afnd "escolhe", "adivinha", o caminho certo para a aceitação, uma vez que a existência de escolhas erradas, que não levam a um estado final, é irrelevante.

Um autômato finito é uma quíntupla, (S, Σ, T, s, A), que consiste de
* Um conjunto finito de estados (S)
* Um conjunto finito desímbolos chamado de alfabeto (Σ)
* Uma função de transição (T: S × Σ → S)
* Um estado inicial (s ∈ S)
* Um conjunto de estados finais (A ⊆ S)
Considere que M seja um AFD tal que M = (S, Σ, T, s, A), e X = x0x1... xn seja uma string contida no alfabeto Σ. M aceita a string X se numa seqüência de estados, r0,r1, ..., rn, existe em S com as seguintes condições:
1. r0 = s
2.ri+1 = T(ri, xi), para i = 0, ..., n-1
3. rn ∈ A.
Conforme mostrado na primeira condição, a máquina inicia no estado inicial s. A segunda condição diz que, dado cada caractere de uma string X, a máquina passará de estado a estado de acordo com a definição de uma função de transição T. A última condição diz que a máquina aceita uma string se a última entrada de X faz com que a máquina passe para um dosestados de aceitação. Caso contrário, dizemos que a máquina rejeitou a string. O conjunto de strings que ela aceita forma uma linguagem, a qual é a linguagem que um AFD reconhece.

Maquinas de Turing
Em 1936, Alan Turing construiu um autômato imaginário, a Máquina de Turing. No seu estudo "Computing machinery and intelligence" (1950), Turing  aborda a  questão da inteligência da máquina,avaliando os argumentos face à possibilidade de criar uma máquina computacional inteligente e sugere respostas para estes argumentos, propondo o Teste de Turing como um teste empírico da inteligência.

A máquina de Turing  pode ser vista como um sofisticado leitor de fitas, com uma fita arbitrariamente extensível. A fita é marcada nas secções, cada secção contém um “1”, um “0” ou ser...
tracking img