Deterministic Finite Automata

Alphabets, Strings, and Languages

Transition Graphs and Tables
Some Proof Techniques

1
 Alphabets
An alphabet is any finite set of
symbols.
Examples:
ASCII, Unicode,
{0,1} (binary alphabet ),
{a,b,c}, {s,o},
set of signals used by a protocol.

2
 Strings

A string over an alphabet Σ is a list, each

element of which is a member of Σ.
 Strings shown with no commas or quotes,
e.g., abc or 01101.
Σ* = set of all strings over alphabet Σ.
The length of a string is its number of
positions.
ε stands for the empty string (string of
length 0).
3
 Example: Strings
{0,1}* = {ε, 0, 1, 00, 01, 10, 11, 000,
001, . . . }
Subtlety: 0 as a string, 0 as a symbol
look the same.
 Context determines the type.

4
 Languages
A language is a subset of Σ* for some
alphabet Σ.
Example: The set of strings of 0’s and
1’s with no two consecutive 1’s.
L = {ε, 0, 1, 00, 01, 10, 000, 001, 010,
100, 101, 0000, 0001, 0010, 0100,
0101, 1000, 1001, 1010, . . . }

Hmm… 1 of length 0, 2 of length 1, 3, of length 2, 5 of length

3, 8 of length 4. I wonder how many of length 5? 5
Deterministic Finite Automata
 A formalism for defining languages,
consisting of:
1. A finite set of states (Q, typically).
2. An input alphabet (Σ, typically).
3. A transition function (δ, typically).
4. A start state (q0, in Q, typically).
5. A set of final states (F ⊆ Q, typically).
 “Final” and “accepting” are synonyms.
6
 The Transition Function
Takes two arguments: a state and an
input symbol.
δ(q, a) = the state that the DFA goes
to when it is in state q and input a is
received.
Note: always a next state – add a dead
state if no transition (Example on next
slide).
7
 Server
s Wins
40-Love s
s s Ad-in
30-Love o s
s 40-15 o
o s o
Start 15-Love 30-15 40-30 s
s s s
o o o
Love 15-all 30-all deuce
o s
s s
o o
15-30 30-40
Love-15 s o
s
o o s
Love-30 15-40
s o
o Ad-out
Love-40 o
o
o Opp’nt
s, o Wins

s, o Dead s, o

8
Graph Representation of DFA’s
Nodes = states.
Arcs represent transition function.
 Arc from state p to state q labeled by all
those input symbols that have transitions
from p to q.
Arrow labeled “Start” to the start state.
Final states indicated by double circles.

9
 Example: Recognizing Strings
Ending in “ing”
Not i or g
Not i Not i or n i

nothing Saw i Saw in Saw ing

i n g

Start i i

Not i
10
Example: Protocol for Sending
Data

timeout
data in
Ready Sending

Start ack

11
Example: Strings With No 11

0 0,1
1 1
A B C

Start 0
String so far String so far Consecutive
has no 11, has no 11, 1’s have
does not but ends in been seen.
end in 1. a single 1.
12
 Alternative Representation:
Transition Table
Final states
starred Columns =
0 1 input symbols
* A A B
Arrow for * B A C
start state C C C
0 0,1
Rows = states
A 1 B 1 C
Each entry is δ
of the row and Start 0
column. 13
Convention: Strings and Symbols
 … w, x, y, z are strings.
 a, b, c,… are single input symbols.

14
 Extended Transition Function
We describe the effect of a string of
inputs on a DFA by extending δ to a
state and a string.
Intuition: Extended δ is computed for
state q and inputs a1a2…an by following
a path in the transition graph, starting
at q and selecting the arcs with labels
a1, a2,…, an in turn.
15
 Inductive Definition of
Extended δ

Induction on length of string.

Basis: δ(q, ε) = q
Induction: δ(q,wa) = δ(δ(q,w),a)
 Remember: w is a string; a is an input
symbol, by convention.

16
Example: Extended Delta
0 1
A A B
B A C
C C C

δ(B,011) = δ(δ(B,01),1) = δ(δ(δ(B,0),1),1) =

δ(δ(A,1),1) = δ(B,1) = C

17
 Delta-hat
We don’t distinguish between the given
delta and the extended delta or delta-
hat.
The reason:
˄ ˄
δ(q, a) = δ(δ(q, ε), a) = δ(q, a)

Extended deltas

18
 Language of a DFA
Automata of all kinds define languages.
If A is an automaton, L(A) is its
language.
For a DFA A, L(A) is the set of strings
labeling paths from the start state to a
final state.
Formally: L(A) = the set of strings w
such that δ(q0, w) is in F.
19
Example: String in a Language
String 101 is in the language of the DFA below.
Start at A.

0 0,1
1 1
A B C

Start 0

20
Example: String in a Language
String 101 is in the language of the DFA below.

Follow arc labeled 1.

0 0,1
1 1
A B C

Start 0

21
Example: String in a Language
String 101 is in the language of the DFA below.

Then arc labeled 0 from current state B.

0 0,1
1 1
A B C

Start 0

22
Example: String in a Language
String 101 is in the language of the DFA below.

Finally arc labeled 1 from current state A. Result

is an accepting state, so 101 is in the language.
0 0,1
1 1
A B C

Start 0

23
 Example – Concluded
The language of our example DFA is:
{w | w is in {0,1}* and w does not have
two consecutive 1’s}

Such that… These conditions

about w are true.
Read a set former as
“The set of strings w…
24
 Proofs of Set Equivalence
Often, we need to prove that two
descriptions of sets are in fact the same
set.
Here, one set is “the language of this
DFA,” and the other is “the set of
strings of 0’s and 1’s with no
consecutive 1’s.”

25
 Proofs – (2)
 In general, to prove S = T, we need
to prove two parts: S ⊆ T and T ⊆ S.
That is:
1. If w is in S, then w is in T.
2. If w is in T, then w is in S.
 Here, S = the language of our running
DFA, and T = “no consecutive 1’s.”

26
 Part 1: S ⊆ T
0 0,1
A 1 B 1C
To prove: if w is accepted by
Start 0
then w has no consecutive 1’s.
Proof is an induction on length of w.
Important trick: Expand the inductive
hypothesis to be more detailed than the
statement you are trying to prove.

27
 The Inductive Hypothesis
1. If δ(A, w) = A, then w has no
consecutive 1’s and does not end in 1.
2. If δ(A, w) = B, then w has no
consecutive 1’s and ends in a single 1.
 Basis: |w| = 0; i.e., w = ε.
 (1) holds since ε has no 1’s at all.
 (2) holds vacuously, since δ(A, ε) is not B.
Important concept:
“length of”
If the “if” part of “if..then” is false, 28
the statement is true.
 0 0,1
Inductive Step A 1 B 1C
Start 0

Assume (1) and (2) are true for strings

shorter than w, where |w| is at least 1.
Because w is not empty, we can write
w = xa, where a is the last symbol of
w, and x is the string that precedes.
IH is true for x.

29
 0 0,1
Inductive Step – (2) A 1 B 1C
Start 0

Need to prove (1) and (2) for w = xa.

(1) for w is: If δ(A, w) = A, then w has no
consecutive 1’s and does not end in 1.
Since δ(A, w) = A, δ(A, x) must be A or B,
and a must be 0 (look at the DFA).
By the IH, x has no 11’s.
Thus, w has no 11’s and does not end in 1.
30
 0 0,1
Inductive Step – (3) A 1 B 1C
Start 0

Now, prove (2) for w = xa: If δ(A, w) =

B, then w has no 11’s and ends in 1.
Since δ(A, w) = B, δ(A, x) must be A,
and a must be 1 (look at the DFA).
By the IH, x has no 11’s and does not
end in 1.
Thus, w has no 11’s and ends in 1.

31
 Part 2: T ⊆ S X

Now, we must prove: if w has no 11’s,

then w is accepted by 0 0,1
Y A 1 B 1C
Start 0
Contrapositive : If w is not accepted by
0 0,1
A 1 B 1C Key idea: contrapositive
of “if X then Y” is the
Start 0
equivalent statement
then w has 11. “if not Y then not X.”
32
 0 0,1
Using the Contrapositive A 1 B 1C
Start 0

Because there is a unique transition

from every state on every input symbol,
each w gets the DFA to exactly one
state.
The only way w is not accepted is if it
gets to C.

33
Using the Contrapositive 0 0,1
– (2) A 1 B 1C
Start 0

The only way to get to C [formally:

δ(A,w) = C] is if w = x1y, x gets to B,
and y is the tail of w that follows what
gets to C for the first time.
If δ(A,x) = B then surely x = z1 for
some z.
Thus, w = z11y and has 11.

34
 Regular Languages
A language L is regular if it is the
language accepted by some DFA.
 Note: the DFA must accept only the strings
in L, no others.
Some languages are not regular.
 Intuitively, regular languages “cannot
count” to arbitrarily high integers.

35
Example: A Nonregular Language
L1 = {0n1n | n ≥ 1}
Note: ai is conventional for i a’s.
 Thus, 04 = 0000, e.g.
Read: “The set of strings consisting of
n 0’s followed by n 1’s, such that n is at
least 1.
Thus, L1 = {01, 0011, 000111,…}
36
 Another Example
L2 = {w | w in {(, )}* and w is balanced }
Balanced parentheses are those
sequences of parentheses that can
appear in an arithmetic expression.
E.g.: (), ()(), (()), (()()),…

37
 But Many Languages are
Regular
They appear in many contexts and
have many useful properties.
Example: the strings that represent
floating point numbers in your favorite
language is a regular language.

38
Example: A Regular Language
L3 = { w | w in {0,1}* and w, viewed as a
binary integer is divisible by 23}
The DFA:
 23 states, named 0, 1,…,22.
 Correspond to the 23 remainders of an
integer divided by 23.
 Start and only final state is 0.

39
 Transitions of the DFA for L3
If string w represents integer i, then
assume δ(0, w) = i%23.
Then w0 represents integer 2i, so we
want δ(i%23, 0) = (2i)%23.
Similarly: w1 represents 2i+1, so we
want δ(i%23, 1) = (2i+1)%23.
Example: δ(15,0) = 30%23 = 7;
δ(11,1) = 23%23 = 0.

40
 Another Example
L4 = { w | w in {0,1}* and w, viewed as the
reverse of a binary integer is divisible by 23}
Example: 01110100 is in L4, because its
reverse, 00101110 is 46 in binary.
Hard to construct the DFA.
But there is a theorem that says the reverse
of a regular language is also regular.

41