UoL CS Notes
Menu

Deterministic Finite Automata (DFAs)

COMP218 Lectures

Here is an example of a finite automaton:

stateDiagram-v2
direction LR
	[*] --> 0p
	5p --> go: +10
	0p --> 5p: +5
	5p --> 10p: +5
	10p --> go: +5, +10
	go --> 0p: R
	0p --> 0p: R
	0p --> 10p: +10
	5p --> 5p: R
	10p --> 10p: R
	go --> go: +5, +10
	go: go
  • There are states and the start state is $\text{0p}$.
  • The automaton takes inputs from $\{+5,+10,R\}$.
  • The state $\text{go}$ is an accepting state.
  • There are transitions saying what to do for every state and every alphabet symbol.

Defining DFAs

A finite automaton (DFA) is a 5 tuple $Q,\Sigma,\delta,q_0,F)$ where:

  • $Q$ is a finite set of states.
  • $\Sigma$ is an alphabet
  • $\delta:Q\times\Sigma\rightarrow Q$ is a transition function.
  • $q_0\in Q$ is the initial state.

  • $F\subseteq Q$ is the set of accepting states (or final states).

    Accepting states should be denoted by double circles. I can only do underlined so I will do that.

Example

stateDiagram-v2
direction LR
	[*] --> q0
	q0 --> q1:1
	q1 --> q2:0
	q0 --> q0:0
	q1 --> q1:1
	q2 --> q2:0,1
	q0: q0
	q1: q1
  • Alphabet: \(\Sigma=\{0,1\}\)
  • States: \(Q=\{q_0,q_2,q_2\}\)
  • Initial State: \(q_0\)
  • Accepting States: \(F=\{q_0,q_1\}\)

  • Table of transition functions $\delta$:

    States Inputs  
      0 1
    $q_0$ $q_0$ $q_1$
    $q_1$ $q_2$ $q_1$
    $q_2$ $q_2$ $q_2$

    Generally we will just draw the state diagram and not the table.

Language of a DFA

The language of a DFA ($Q,\Sigma,\delta,q_0,F$) is the set of all strings over $\Sigma$ that, starting from $q_0$ and following tha transitions as the string is read from left to right, will reach some accepting state.

This basically means that the language of a DFA is a valid path on a DFAs state diagram that ends at an accepting state.

For additional examples for DFA languages see this video.

Ends With… Example

For examples on DFAs that accept strings that end with … see this video.

One example given ends with the string $\{0,1\}$. For this you’d need the following graph:

stateDiagram-v2
	direction LR
	[*] --> q0:0
	[*] --> q1:1
	q0 --> q00:0
	q0 --> q01:1
	q1 --> q10:0
	q1 --> q11:1
	q00 --> q00:0
	q00 --> q01:1
	q01 --> q10:0
	q01 --> q11:1
	q10 --> q01:1
	q10 --> q00:0
	q11 --> q10:0
	q11 --> q11:1
	q01:q01

To do this you make a tree of options up to the length of the given string and then loop back around.