0.Introduction: Terminology§

Finite State Machine

Finite State Automata

Finite Automata

Automata: This just means “machine”

All names for a simple model of computation that has:
* States that the machine can be in (nodes)
* Input (string)
* Transitions on a character between states (edges)
* Some machine types have memory

Deterministic Finite Acceptor

Our simplest machine.

Deterministic: In a state, when given a specific letter,
only one thing to do.
Finite: Finite number of states
Acceptor: It only decides whether or not a string is in this
machine’s language (so it has no ability to modify the tape)

input tape

tape head

current state

head moves

DFA: Formal Definition

Define a DFA as $(Q, \Sigma, \delta, q_0, F)$ where

$Q$ is a finite set of states
$\Sigma$ is the input alphabet (a finite set)
$\delta: Q \times\Sigma \rightarrow Q$ . A set of transitions like $(q_i, a) \rightarrow q_j$ meaning that when in state $q_i$ , if you see letter $a$ , consume it and go to state $q_j$ .
$q_0$ is the initial state ( $q_0 \in Q$ )
$F \subseteq Q$ is a set of final states

Concept: Accepting a String

Example: A DFA that accepts even binary numbers.

Assign meaning to the states: q0 - odd numbers, q1 - even numbers,
Note the arrow: Start State
Note the double circle: Accepting State

We accept the string if we halt (finish the string) in an accepting state.

Formal Definition

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

Tabular Format

$\begin{split}\begin{array}{r|cc} & 0 & 1 \\ \hline q0 & & \\ q1 & & \\ \end{array}\end{split}$

Example

.

Concept: Power of DFAs

A given DFA can accept a set of strings: A language.
All of the possible DFAs form a class of machines.
So DFAs (as a class of machines) can accept certain languages
(as a matching class of langauges).

Algorithm for DFA

Start in start state with input on tape
q = current state
s = current symbol on tape
while (s != blank) do
q=δ(q,s)
s = next symbol to the right on tape
if q∈F then accept

Trace

Example of a trace: 100

Definitions

$\lambda$ (lambda): The empty string

${\delta}^{*}(q,\lambda)=q$

You didn’t go anywhere, you are still in state

$q$

${\delta}^{*}(q_i,w)= q_j$

Given string

$w$ and starting in state

$q_i$ , we will reach state

$q_j$ .

${\delta}^{*}(q,wa)={\delta}({\delta}^{*}(q,w),a)$

Apply

$\delta$ to all of

$w$ first (some string) and then to

$a$

The language accepted by a DFA

$M = (Q, \Sigma, \delta, q_0, F)$ is set of all strings on

$\Sigma$ accepted by

$M$ .

Formally,

$L(M) = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\in F\}$

Set of strings not accepted:

$\overline{L(M)} = \{w\in{\Sigma}^{*}\mid {\delta}^{*}(q_0,w)\not\in F\}$

Incomplete DFA

Note that our DFA for even binary numbers is “complete”.

We always know what to do on any input.

Consider the language $L(M) = \{b^na | n > 0\}$

This is technically incomplete. It shows all ways that we can reach an accepting state.

Trap State

Can complete by adding one or more “trap” states with the “extra” transitions.

trap

a,b

There is nothing “special” about the trap state, they are just conceptual.

A “trap” state means that once in, all transitions keep us there.

A “final” trap state is any trap state that is a final. Example: Define a machine that accepts any string that starts with “ab”.

Regular Languages

Definition: Given some class or type of Finite Acceptors, the set of languages accepted by that class of Finite Acceptors is called a family.

Definition: Therefore, the DFAs define a family of languages that they accept. A language is regular if and only if there exists a DFA $M$ such that $L = L(M)$ .