Deterministic Finite Automata

In order to describe a Deterministic Finite Automation, $\boxed{\text{DFA}}$, we describe 5 things:

• its states
• its input alphabet
• its (unique) initial state
• its favourable (or accepting) states there can be none, or more than one
• its transition function: for every (state, input symbol) pair we have to tell what the next state should be

A word $w$ is accepted by DFA $A$ if the computation of $A$ on input $w$ ends up in some favourable state. Otherwise, $w$ is rejected by $A$.

Link to original

DFA Minimisation

Mainstream method for optimising DFAs:

1. Take all pairs $(q,p)$ with $q\ne p$
2. Mark all pairs that have accepting and non-accepting states
3. For all unmarked pairs $(q,p)$ and all characters $c$ test whether $(\delta (q,c),\delta (p,c))$ are marked. If yes in at least one case, then also mark $(q,p)$.
4. Repeat last step until no change.
5. All unmarked pairs can be merged.

Example

After iterating through all the pairs: Which leaves us with: