Slide 1
Finite State Machines
Chapter 5
Languages and Machines
Regular Languages
Regular Language
Regular Expression
Finite State Machine
L
Accepts
Finite State Machines
An FSM for a vending machine:
One soda (S) is $.25
No pennies
Max credit $.45
Definition of a DFSM
M = (K, , , s, A), where:
K is a finite set of states
is an alphabet
s K is the initial state
A K is the set of accepting (final) states, and
is the transition function from (K ) to K
Accepting by a DFSM
Informally, M accepts a string w iff M winds up in some element of A when it has finished reading w.
The language accepted by M, denoted L(M), is the set of all strings accepted by M.
Configurations of DFSMs
A configuration of a DFSM M is an element of:
K *
It captures the two things that can make a difference to M’s future behavior:
• its current state
• the input that is still left to read.
The initial configuration of a DFSM M, on input w, is:
(s, w)
The Yields Relations
The yields-in-one-step relation |-M:
(q, w) |-M (q’, w’) iff
• w = a w’ for some symbol a , and
• (q, a) = q’
|-M * is the reflexive, transitive closure of |-M.
Computations Using FSMs
A computation by M is a finite sequence of configurations C0, C1, …, Cn for some n 0 such that:
• C0 is an initial configuration,
• Cn is of the form (q, ), for some state q KM,
• C0 |-M C1 |-M C2 |-M … |-M Cn.
Accepting and Rejecting
A DFSM M accepts a string w iff:
(s, w) |-M * (q, ), for some q A.
A DFSM M rejects a string w iff:
(s, w) |-M* (q, ), for some q A.
The language accepted by M, denoted L(M), is the set of all strings accepted by M.
Theorem: Every DFSM M, on input s, halts in |s| steps.
An Example Computation
An FSM to accept odd integers:
even odd
even
q0 q1
odd
On input 235, the configurations are:
(q0, 235) |-M (q0, 35)
|-M
|-M
Thus (q0, 235) |-M* (q1, )
Regular Languages
A language is regular iff it is accepted by some FSM.
A Very Simple Example
L = {w {a, b}* :
every a is immediately followed by a b}.
A Very Simple Example
L = {w {a, b}* :
every a is immediately followed by a b}.
Parity Checking
L = {w {0, 1}* : w has odd parity}.
Parity Checking
L = {w {0, 1}* : w has odd parity}.
No More Than One b
L = {w {a, b}* : w contains at most one b}.
No More Than One b
L = {w {a, b}* : w contains at most one b}.
Checking Consecutive Characters
L = {w {a, b}* :
no two consecutive characters are the same}.
Checking Consecutive Characters
L = {w {a, b}* :
no two consecutive characters are the same}.
Dead States
L =
{w {a, b}* : every a region in w is of even length}
Dead States
L =
{w {a, b}* : every a region in w is of even length}
Dead States
L =
{w {a, b}* : every b in w is surrounded by a’s}
The Language of Floating Point Numbers is Regular
Example strings:
+3.0, 3.0, 0.3E1, 0.3E+1, -0.3E+1, -3E8
The language is accepted by the DFSM:
DFSMs are complete
The transition function is always complete
The missing transitions are leading to a “dead” state
Often not shown for clarity
E,.
+,-,E,.
+,-,E
+,-,E,.
+,-,E,.
+,-,.
E,.
+,-,E,.
+,-,d,E,.
dead
state
A Simple Communication Protocol
Controlling a Soccer-Playing Robot
A Simple Controller
Programming FSMs
Cluster strings that share a “future”.
Let L = {w {a, b}* : w contains an even number of a’s and an odd number of b’s}
*
Even a’s Odd b’s
Vowels in Alphabetical Order
L = {w {a – z}* : all five vowels, a, e, i, o, and u,
occur in w in alphabetical order}.
Vowels in Alphabetical Order
L = {w {a – z}* : all five vowels, a, e, i, o, and u,
occur in w in alphabetical order}.
Complementing FSMs
L = {w {a, b}* : w does not contain the substring aab}.
*
Start by building an FSM for not L. Then swap accepting and nonaccepting states.
Note that this foreshadows the claim that we will make later that the regular languages are closed under complement.
Complementing FSMs
L = {w {a, b}* : w does not contain the substring aab}.
Start with a machine for L:
How must it be changed?
A Building Security System
L = {event sequences such that the alarm should sound}
FSMs Predate Computers
The Antikythera mechanism (Greece, 80 BC)
FSMs Predate Computers
The Prague Orloj, originally built in 1410.
FSMs Predate Computers
The abacus
The Jacquard Loom (1801)
FSMs Predate Computers
The Missing Letter Language
Let = {a, b, c, d}.
Let LMissing =
{w : there is a symbol ai not appearing in w}.
Try to make a DFSM for LMissing:
*
Try it deterministically.
Definition of an NDFSM
A nondeterministic FSM (NDFSM) is
M = (K, , , s, A), where:
K is a finite set of states
is an alphabet
s K is the initial state
A K is the set of accepting states, and
is the transition relation. It is a finite subset of
(K ( {})) K
Accepting by an NDFSM
M accepts a string w iff there exists some path along which w drives M to some element of A.
The language accepted by M, denoted L(M), is the set of all strings accepted by M.
Sources of Nondeterminism
Two approaches:
• Explore a search tree:
• Follow all paths in parallel
Analyzing Nondeterministic FSMs
Optional Substrings
L = {w {a, b}* : w is made up of an optional a followed by aa followed by zero or more b’s}.
Multiple Sublanguages
L = {w {a, b}* : w = aba or |w| is even}.
The Missing Letter Language
Let = {a, b, c, d}. Let LMissing = {w : there is a symbol ai not appearing in w}
The Missing Letter Language
Pattern Matching
L = {w {a, b, c}* : x, y {a, b, c}* (w = x abcabb y)}.
A DFSM:
Pattern Matching with NDFSMs
L = {w {a, b, c}* : x, y {a, b, c}* (w = x abcabb y)}.
An NDFSM:
Multiple Keywords
L = {w {a, b}* :
x, y {a, b}* : w = x abbaa y or
w = x baba y }
Multiple Keywords
L = {w {a, b}* :
x, y {a, b}* : w = x abbaa y or
w = x baba y }
Checking from the End
L = {w {a, b}* :
the fourth to the last character is a}
Checking from the End
L = {w {a, b}* :
the fourth to the last character is a}
*
Try it with aabaaa.
Another Pattern Matching Example
L = {w {0, 1}* : w is the binary encoding of a positive integer that is divisible by 16 or is odd}
Another NDFSM
L1= {w {a, b}* : aa occurs in w}
L2= {x {a, b}* : bb occurs in x}
L3= {y {a, b}* : y L1 or L2 }
M1 =
M2=
M3=
Analyzing Nondeterministic FSMs
Does this FSM accept:
baaba
Remember: we just have to find one accepting path.
Two approaches:
Explore a search tree
Follow all paths in parallel
{1} {2,3} {2,3,4} {2,3,4} {2,3} {2,3,4}
Analyzing Nondeterministic FSMs
1,baaba
2,aaba
3,aaba
2,aba
4,aba
3,aba
2,ba
4,ba
3,ba
3,a
3,a
2,a
3,ε
3,ε
4,ε
b
a
a
b
a
2,ε
Dealing with Transitions
ε-transitions change state without using input symbols
eps(q) = {p K : (q, w) |-*M (p, w)}.
eps(q) is the closure of {q} under the relation
{(p, r) : there is a transition (p, , r) }.
How shall we compute eps(q)?
An Algorithm to Compute eps(q)
Compute eps(q: state)
result = {q}.
While there exists some p result and
some r result and
some transition (p, , r) do:
Insert r into result.
Return result.
p
r
result
q
An Example of eps
eps(q0) = {q0,q1,q2}
eps(q1) = {q0,q1,q2}
eps(q2) = {q0,q1,q2}
eps(q3) = {q3}
Simulating a NDFSM
ndfsmsimulate(M: NDFSM, w: string) =
current-state = eps(s).
For each c symbol of w do:
next-state = .
For each state q in current-state do:
For each state p such that (q, c, p) do:
next-state = next-state eps(p).
current-state = next-state.
If current-state contains states in A, then accept.
else reject.
Example
a
0
1
2
3
4
5
6
b
b
a
ε
ε
a,b
0,1,4
0,1,2,4
0,1,4,5
0,1,4,5,6
a
b
w = abb
eps(0) = {0,1,4}
for 1 ≤ i ≤ 6,
eps(i) = { i }
b
Nondeterministic and
Deterministic FSMs
Clearly: {Languages accepted by a DFSM}
{Languages accepted by a NDFSM}
More interestingly:
Theorem 5.3:
For each NDFSM, there is an equivalent DFSM.
Nondeterministic and
Deterministic FSMs
Proof: By construction:
Given a NDFSM M = (K, , , s, A),
we construct M’ = (K’, , ’, s’, A’), where
K’ = P(K)
s’ = eps(s)
A’ = {Q K : Q A }
'(Q, a) = {eps(p): p K and
(q, a, p) for some q Q}
An Algorithm for Constructing the Deterministic FSM
1. Compute the eps(q)’s.
2. Compute s’ = eps(s).
3. Compute ’.
4. Compute K’ = a subset of P(K).
5. Compute A’ = {Q K’ : Q A }.
The Algorithm ndfsmtodfsm
ndfsmtodfsm(M: NDFSM) =
1. For each state q in K do:
1.1 Compute eps(q).
2. s’ = eps(s)
3. Compute ’:
3.1 active-states = {s’}.
3.2 ’ = .
3.3 While Q active-states, c with ’(Q,c) unknown do:
new-state = .
For each state q in Q do:
For each state p such that (q, c, p) do:
new-state = new-state eps(p).
’ (Q,c) = new-state
active-states = active-states { new-state }
4. K’ = active-states.
5. A’ = {Q K’ : Q A }.
Example
a
0
1
2
3
4
5
6
b
b
a
ε
ε
a,b
0,1,4
0,1,2,4
0,1,4,5
0,1,2,3,4
0,1,4,5,6
a
a
a
b
b
b
b
a
b
a
eps(0) = {0,1,4}
for 1 ≤ i ≤ 6,
eps(i) = { i }
The Number of States May Grow Exponentially
No. of states after 0 chars: = 1
No. of new states after 1 char: = n
No. of new states after 2 chars: = n(n-1)/2
No. of new states after 3 chars: = n(n-1)(n-2)/6
Total number of states after n-1 chars: 2n – 1
|| = n
Another Hard Example
L = {w {a, b}* :
the fourth to the last character is a}
n
n
–
æ
è
ç
ö
ø
÷
1
n
n
–
æ
è
ç
ö
ø
÷
2
n
n
–
æ
è
ç
ö
ø
÷
3