Home CPSC 326

Deterministic Finite Automata

Overview

DFAs are the simplest computational model we will consider. The "memory" of a DFA is limited to the state it is currently in. At each state, an input can move it into another state.

For example the following DFA accepts $.50 in exact change.

Note that:

The way that DFAs "compute" is by either accepting or rejecting their input according to their state rules.


DFA Definition

A DFA is composed by the following 5 things:
  1. $Q$, the set of states.
  2. $\Sigma$, the alphabet.
  3. $\delta: Q \times \Sigma \rightarrow Q$, the transition function.
  4. $q_0 \in Q$, the start state.
  5. $F \subseteq Q$, the accept states.

For the example DFA above, we have:

  1. $Q = \{0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, R\}$
  2. $\Sigma = \{N, D, Q\}$
  3. $\delta$ can be given as::
     NDQ
    051025
    5101530
    10152035
    15202540
    20253045
    25303550
    303540R
    354045R
    404550R
    4550RR
    50RRR
    RRRR
    Where the first column is the current state, and the next columns indicate which state to transition to with the given input.
  4. $q_0 = 0$
  5. $F = \{50\}$

Examples

What is the formal definition of the following DFA?

What about the following DFA?


Languages

We say that DFA $M$ accepts string $w$ iff $M$ ends up in an accept state when it has finished reading $w$.

We say that the language of $M$, written as $L(M)$ is the set of all strings denoted accepted by $M$. We also say that $L$ is recognized by $M$.

What is the language of the following DFA?

What about the following DFA?

Any language that is recognized by some DFA is said to be regular.


The Language of Floating Point Numbers

The language of floating-point numbers in typical programming languages is regular.

Examples:

Here "d" refers to any digit 0-9

Compilers do in fact use finite automata for recognizing patterns like this.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.