Deterministic Finite Automaton

Aka. DFA. Has a single starting state.

Transition Function

Denoted by $\delta: Q \times \Sigma \rightarrow Q$. It maps a state and an input symbol to the next state.

Extended Transition Function

Denoted by $\delta^*$. Handles strings instead of each symbol. $\delta^*(q, x)$ is the state reached after reading string $x$ starting from state $q$.

Rules:

• $\delta^*(q, \lambda) = q$
• $\delta^*(q, ya) = \delta (\delta^*(q, y), a)$

Acceptance

Let $M = (Q, \Sigma, q_0, A, \delta)$.

A string $x \in \Sigma^*$ is accepted iff $\delta^*(q_0, x) ∈ A$.

Incomplete

A DFA is incomplete iff $\delta(q,a)$ is undefined for some $q$ and $a$. Inputs with undefined transitions are implicitly rejected.

Complement

Complement of a complete DFA $M = (Q, \Sigma, q_0, A, \delta)$ is:

When complementing an incomplete DFA, a dead/sink state $d$ must be added. For all undefined transitions, $\delta(q, a) = d$ must be defined.