5. Deterministic Finite Automata

Deterministic Finite Automata

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

What does ‘deterministic’ mean?

Taking this diagram from earlier:

digraph {
	label=A₁
	rankdir=LR
	init[shape=point]
	node[shape=doublecircle]; q;
	node[shape=circle];
	init->s
	s->s [label=a]
	s->q [label=b]
	q->q [label=b]
	q->r [label=a]
	r->r [label=a]
	r->r [label=b]
}

Deterministic means that for each state and symbol, there is a unique arrow coming out of the state labelled by the symbol.

As it is unique, there is one, but not more than one. We can say that, the pair $(\text{current state},\text{symbol read})$ uniquely determines the next state. This is why DFAs are called deterministic. DFAs will never “get stuck”, it never has to choose.

Transition Table

From $A_1$ above, we find that:

• States: $s,q,r$
• Input alphabet: $\{a,b\}$
• Initial state: $s$
• Favourable states: $q$

The transition table is another way of representing the transition function of $A_1$:

	$a$	$b$
$s$	$s$	$q$
$q$	$r$	$q$
$r$	$r$	$r$

For each cell in the table, there is a unique state to put in. As before, the pair uniquely indetifies the next state.