Aula AFD AFND

Autˆomatos Finitos
Renato E. N. Moraes
Universidade Federal do Esp´ırito Santo

Abril 2015

Renato E. N. Moraes, UFES

Autˆ omatos Finitos

1/31

Conte´udo

Autˆ omato finito

Autˆ omato finito determin´ıstico

Linguagem de autˆ omato finito determin´ıstico

Autˆ omato finito N˜ao Determin´ıstico

Renato E. N. Moraes, UFES

Autˆ omatos Finitos

2/31

Conte´udo

Autˆ omato finito

Autˆ omato finito determin´ıstico

Linguagem de autˆ omato finito determin´ıstico

Autˆ omato finito N˜ao Determin´ıstico

Renato E. N. Moraes, UFES

Autˆ omatos Finitos

3/31

Autˆomato finito

Defini¸c˜ao
Autˆ
omato finito ´e um procedimento (ou m´aquina) que s´o pode conter uma quantidade finita e limitada de informa¸c˜ao a qualquer momento.
Essa informa¸c˜ao ´e representada por um estado da m´aquina, e s´o existe um n´ umero finito de estados.
Um procedimento ´e uma sequˆencia finita de instru¸c˜ oes claramente descritas, que podem ser executadas mecanicamente em tempo finito. mecanicamente: n˜ ao h´ a d´ uvidas sobre o que ser feito em tempo finito: n˜ ao h´ a d´ uvidas de que a instru¸c˜ ao pode ser levada at´e sua conclus˜ ao Renato E. N. Moraes, UFES

Autˆ omatos Finitos

4/31

Conte´udo

Autˆ omato finito

Autˆ omato finito determin´ıstico

Linguagem de autˆ omato finito determin´ıstico

Autˆ omato finito N˜ao Determin´ıstico

Renato E. N. Moraes, UFES

Autˆ omatos Finitos

5/31

Autˆomato finito determin´ıstico
Defini¸c˜ao
Um Autˆ omato finito determin´ıstico M, sobre um alfabeto Σ ´e um sistema (K , Σ, δ, i, F ), onde
K ´e um conjunto de estados finito, n˜ao vazio;
Σ ´e um alfabeto de entrada (finito) δ : K × Σ → K ´e a fun¸c˜ao de transi¸c˜ao i ∈ K ´e o estado inicial
F ⊆ K ´e o conjunto de estados finais.
Diz-se determin´ıstico pois: δ ´e uma fun¸c˜ ao que determina o pr´ oximo estado a ser assumido quando a m´ aquina M se encontra no estado q e lˆe da entrada o s´ımbolo a: o estado δ(q, a)

Renato E. N. Moraes, UFES

Autˆ omatos Finitos

6/31

Autˆomato finito