Deterministic Finite Automata DFA

 

💡 What is a Deterministic Finite Automaton (DFA)?

A DFA is a simple mathematical model of a computer with limited memory that reads strings and decides whether they belong to a language.

It's called:

• Finite → because it has a finite number of states.

• Automaton → because it's an abstract machine.

• Deterministic → because for every state and input symbol, there is exactly one transition.

---

🔢 Formal Definition of a DFA

A DFA is a 5-tuple:

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

Where:

Component	Meaning
$Q$	Finite set of states
$\Sigma$	Finite set of input symbols (alphabet)
$\delta$	Transition function: $Q \times \Sigma \rightarrow Q$
$q_0$	Start state, where the machine begins
$F \subseteq Q$	Set of accepting (final) states

🧠 DFA Behavior:

• It starts in the initial state $q_0$

• Reads the input string one symbol at a time

• Based on current state and input symbol, it moves to a new state

• When input ends:

  • If it’s in a final state, the string is accepted

  • Otherwise, the string is rejected

---

✅ Key Properties of a DFA

1. Determinism: No ambiguity — exactly one transition for each symbol from a state.

2. Memoryless: The only "memory" is the current state.

3. Complete transition function: For every state and symbol, a transition must be defined.

4. Recognizes Regular Languages: DFAs define or recognize all and only the regular languages.

---

📘 Example

Let’s define a DFA that accepts all strings over {0, 1} ending with 1.

• $Q = \{q_0, q_1\}$
  

• $\Sigma = \{0, 1\}$
  

• $q_0 =$ start state

• $F=\{q_1\}$

• Transition function $\delta$:

Current State	Input	Next State
$q_0$	0	$q_0$
$q_0$	1	$q_1$
$q_1$	0	$q_0$
$q_1$	1	$q_1$

This DFA remembers the last symbol — if it’s a 1, it accepts.