Autômatos finitos determinísticos
Origem: Wikipédia, a enciclopédia livre.
Dentro da Teoria da Computação, uma máquina de estados finitos determinística ou autômato finito determinístico é uma máquina de estados finitos onde, para cada par de estados e símbolo de entrada, existe um próximo estado determinístico.
[editar] Definição formal
Um autômato finito determinístico é uma quíntupla, (S, Σ, T, s, A), que consiste de
- um conjunto finito de estados (S)
- um conjunto finito de sí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 (ou DFA) 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:
- r0 = s
- ri+1 = T(ri, xi), para i = 0, ..., n-1
- rn ∈ A.
Conforme mostrado na primeira condição, a máquina inicia no estado inicial s. A segunda condição diz que, dado cada caracter 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 dos estados 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.
[editar] Exemplo
O exemplo a seguir é um autômato finito determinístico M, que possui um alfabeto binário, o qual determina se a entrada contém um número igual de 0's.
M = (S, Σ, T, s, A) onde
- Σ = {0, 1},
- S = {S1, S2},
- s = S1,
- A = {S1}, and
- T é definido pela seguinte tabela de transição de estados:
|
|
|
|
| S1 | S2 | S1 |
| S2 | S1 | S2 |
Considerando o autômato de maneira simplificada, o estado S1 representa que havia realmente um número par de 0's, enquanto S2 significa um número ímpar. Um '1' na entrada não muda o estado do autômato. Quando a entrada é consumida, o estado irá indicar se a entrada continha ou não um número par de 0's.
A linguagem de M pode ser descrita pela linguagem regular dada por essa expressão regular:
| Teoria de Autômatos: Linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
| -- | Estrutura de frase | Recursiva | Máquina de Turing |
| Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |
