Deterministic Finite Automata

Deterministic Finite Automata (DFA)

A type of Finite Automaton which is deterministic. This means that the transition Function $Q$ contains only one output for each character from each node. So you know exactly, the next step given a character and state. It has the same definition as FA, just with a more restrictive definition of $\delta$.

Is also a subset of NFAs

Definition

A deterministic finite automaton is a 5-Tuple ($Q,\sum ,\delta ,q_0,F$)

1. $Q$: a finite set of states
2. $\sum$: a finite alphabet
3. $\delta$: $Q\times \sum \to Q$: a transition function (the Cartesian Product between $Q$ and $\sum$)
4. $q_{0\in }Q$: the starting state
5. $F\subseteq Q$: a set of accepting states

Example 1

This DFA has the following properties:

1. $Q=\{q_0,q_1\}$
2. $\sum =\{0,1\}$
3. $\delta =\begin{array}{ccc}& 0& 1\\ q_0& q_0& q_1\\ q_1& q_1& q_0\end{array}$
4. $q_0$ is the starting state
5. $F=\{q_1\}$ are the success states

What language does this state machine accept? Any string with an odd number of $1$s.