Os Autômatos Matemática

Universidade Veiga de Almeida                                     Matemática Discreta II

Professora: Ana Maria Vianna

Autômatos

Finitos

Realizado por Bernardo J. C. Nunes                                         

Terça-feira,  06/05/2014

1. Introdução

        1.1. Definição

Um autômato finito é uma máquina capaz de reconhecer padrões em uma entrada feita de caracteres de um alfabeto. O papel do AF é interpretar esta entrada e aceita-la caso um padrão seja reconhecido ou rejeita-la caso contrário.

É possível representar um AF por grafos, onde os nódulos são estados e as arestas transições.

Exemplo:         [pic 1]

2. Tipos de Autômatos Finitos

        2.1. Determinístico (AFD)

Um AFD ‘M’ sobre um alfabeto ‘Σ’ é constituído pelo sistema:

M = (K, Σ, δ, i, F), onde:

                K : conjunto estados (finito e não vazio);

                Σ : alfabeto de entrada (finito e não vazio);

δ : função de transição δ: K x Σ → K;

                i : é o estado inicial (onde i ∈ K);

                F : é o conjunto dos estados finais (onde F ⊆ K);

        Um AFD aceita uma cadeia se, partindo do estado inicial (i) e mudando de estado de acordo com a função de transição, o AFD atinge um estado final ao terminar de ler a cadeia.

São determinísticos os AF onde para cada símbolo da cadeia de entrada exista somente um estado para o qual a máquina pode transitar.

Exemplo:

Considerando o seguinte AFD:

K = { q0, q1, q2, q3 }

Σ  = { a, b }

I   = q0

F  = { q3 }

A função de transição δ: { q0, q1, q2, q3 } × { a, b } → { q0, q1, q2, q3 } é dada pela tabela:[pic 2]

|  δ  |  a  |  b   |

| q0 | q1 | q2 |

| q1 | q0 | q3 |             →

| q2 | q3 | q0 |

| q3 | q2 | q1 |

2.2. Não-Determinístico (AFND)

Diferente do que acontece com o AFD, a função de transição de um AFND não precisa determinar exatamente qual deve ser o próximo estado. Ao invés disso, a função de transição fornece uma lista (em forma de conjunto) dos possíveis estados para os quais a transição poderá ser feita. Esta lista pode ou não ser vazia.