Deterministic Finite Accepters (DFA)

Formal Definition

A deterministic finite accepter or DFA is defined by the quintuple

$$ M = (Q, \Sigma, \delta, q_0, F), $$

where:

• $Q$ is a finite set of internal states,
• $\Sigma$ is a finite set of symbols called the input alphabet,
• $\delta : Q \times \Sigma \rightarrow Q$ is a total function called the transition function,
• $q_0 \in Q$ is the initial state,
• $F \subseteq Q$ is a set of final (accepting) states.

<aside> 💡 For example, if we have $\delta(q_0, a) = q_1$, then if the dfa is in state $q_0$ and the current input symbol is $a$, the dfa will go into state $q_1$.

</aside>

Transition Graphs

We use transition graphs to visually represent finite automata.

• Vertices represent states; labels on vertices are state names.
• Edge represent transitions, an edge $(q_0, q_1)$ labeled $a$ represents the transition $\delta(q_0, a) = q_1$.

Extended Transition Function

The extended transition function has definition