- DFA refere-se a autômatos finitos determinísticos. Determinístico refere-se à singularidade da computação. Os autômatos finitos são chamados de autômatos finitos determinísticos se a máquina lê uma string de entrada, um símbolo por vez.
- No DFA, existe apenas um caminho para entrada específica do estado atual para o próximo estado.
- O DFA não aceita o movimento nulo, ou seja, o DFA não pode mudar de estado sem qualquer caractere de entrada.
- O DFA pode conter vários estados finais. É usado em Análise Lexical no Compilador.
No diagrama a seguir, podemos ver que do estado q0 para a entrada a, existe apenas um caminho que vai para q1. Da mesma forma, de q0, existe apenas um caminho para a entrada b indo para q2.
Definição formal de DFA
Um DFA é uma coleção de 5 tuplas iguais às descritas na definição de FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
A função de transição pode ser definida como:
δ: Q x ∑→Q
Representação Gráfica do DFA
Um DFA pode ser representado por dígrafos chamados diagrama de estado. No qual:
- O estado é representado por vértices.
- O arco rotulado com um caractere de entrada mostra as transições.
- O estado inicial está marcado com uma seta.
- O estado final é indicado por um círculo duplo.
Exemplo 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Solução:
Diagrama de Transição:
Tabela de Transição:
| Estado atual | Próximo estado para entrada 0 | Próximo estado da entrada 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Exemplo 2:
DFA com ∑ = {0, 1} aceita todos começando com 0.
Solução:
Explicação:
- No diagrama acima, podemos ver que dado 0 como entrada para o DFA no estado q0 o DFA muda de estado para q1 e sempre vai para o estado final q1 ao iniciar a entrada 0. Ele pode aceitar 00, 01, 000, 001... .etc. Ele não pode aceitar nenhuma string que comece com 1, porque nunca irá para o estado final em uma string que comece com 1.
Exemplo 3:
DFA com ∑ = {0, 1} aceita todos que terminam em 0.
Solução:
Explicação:
No diagrama acima, podemos ver que dado 0 como entrada para o DFA no estado q0, o DFA muda de estado para q1. Ele pode aceitar qualquer string que termine com 0, como 00, 10, 110, 100....etc. Ele não pode aceitar nenhuma string que termine com 1, pois nunca irá para o estado final q1 em 1 entrada, então a string que termina com 1 não será aceita ou será rejeitada.