0.3. Deterministic Finite Acceptors¶

0.3.1. Deterministic Finite Acceptors¶

0.3.1.1. 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

0.3.1.2. 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
a
a
b
b
a
b
tape head
current state
1
0
head moves

0.3.1.3. 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

0.3.1.4. Concept: Accepting a String¶

Example: A DFA that accepts even binary numbers.

q0
q1
0
1
1
0

Assign meaning to the states: q0 - odd numbers, q1 - even numbers,

Note the triangle: Start State

Note the double circle: Final (Accepting) State

We accept the string if we halt (finish the string) in a final state.

0.3.1.5. 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}$

0.3.1.6. Example¶

Your browser does not support iframes.

0.3.1.7. .¶

.

0.3.1.8. 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).

0.3.1.9. Algorithm for DFA¶

Start in start state with input on tape

q = current state

s = current symbol on tape

while (s != blank) do

$q = \delta(q,s)$

s = next symbol to the right on tape

if $q \in F$ then accept

0.3.1.10. Trace¶

Example of a trace: 100

1)
1
0
0
q0
q1
2)
1
0
0
q0
q1
3)
1
0
0
q0
q1
4)
1
0
0
q0
q1

0.3.1.11. 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\}$

0.3.1.12. 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\}$

q0
q1
q2
b
a
b

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

0.3.1.13. Trap State¶

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

q0
q1
q2
trap
b
a
a,b
a,b
a
b

There is nothing “special” about a 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”.

0.3.1.14. 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)$ .

CS4114 Coursenotes

Chapter 0 Week 1

0.3. Deterministic Finite Acceptors¶

0.3.1. Deterministic Finite Acceptors¶

0.3.1.1. Introduction: Terminology¶

0.3.1.2. Deterministic Finite Acceptor¶

0.3.1.3. DFA: Formal Definition¶

0.3.1.4. Concept: Accepting a String¶

0.3.1.5. Formal Definition¶

0.3.1.6. Example¶

0.3.1.7. .¶

0.3.1.8. Concept: Power of DFAs¶

0.3.1.9. Algorithm for DFA¶

0.3.1.10. Trace¶

0.3.1.11. Definitions¶

0.3.1.12. Incomplete DFA¶

0.3.1.13. Trap State¶

0.3.1.14. Regular Languages¶