Transcript ECE-548 Sequential Machine Theory

Equivalence, DFA, NDFA
Sequential Machine Theory
Prof. K. J. Hintz
Department of Electrical and Computer
Engineering
Lecture 2
Updated and modified by Marek
Perkowski
Equivalence Relation on A
• An Equivalence Relation (Not Relationship)
Is Not an Equality Relation
• A Relation is an Equivalence Relation if
and only if (iff) it is:
– Reflexive
– Symmetric
– Transitive
Equivalence Relation on A
if
 a, a R
 a , a ' A
and
 a, a ' R   a ' , a R  a, a 'A
and
 a, a ' R,
 a ' , a ' ' R   a, a ' ' R
then
R is an equivalence relation~  on A
(reflexive)
(symmetric)
 a , a ' , a ' ' A (transitive)
Non-Algebraic Equivalence
Relation Example
Equivalence Relation on the Set of All
Triangles on a Plane
“is congruent to” or “is similar to”
– Reflexive, each triangle is similar to itself,
Equivalence Relation Example
Symmetric, if
is similar to
then
is similar to
Equivalence Relation Example
Transitive, if
is similar to
and
is similar to
then
is similar to
Inclusion Relation
Given 2 partit ionsdefined on theset of states,S,
 i   B i1 , B i 2 , B i 3 ,  
 j  B j1 , B j 2 , B j 3 , 
then
i   j
(read as "  i is included in  j " )
iff
all states B i are also  B  j B   i ,  j
Inclusion Relation Example
let

1  1,2, 3, 4, 5

B11  1, 2 , B12  3 , B13   4 , B14  5 

and  2  1,2,3, 4,5

then
1   2 ,
or,
1 " is included in"  2 ,
Partition Notation
• Overbar Indicates States Which Are Elements of
the Same -block.
• Single States Are Not Normally Listed
1   1 2, 3, 4, 5 
B11   1, 2  B12   3  B13   4  B14   5 
is written as
1   1 2  and  2   1 2 3, 4 5 
Relations May Be Orderings
• Partial Ordering
• Total Ordering, aka Chain
• Well Ordering (not discussed here)
Partial Ordering
• Given an Inclusion Relation, R: s  s’,
Defined on some Elements of the Set S such
that s, s’  S, R Is a Partial Ordering If It
Is:
–
–
–
–
Reflexive
Anti-Symmetric (asymmetric)
Transitive
Not all orderings are specified, therefore partial
Properties of PO
– Reflexive
•s
 s for all s  S
– Anti-Symmetric (asymmetric)
If
s  s
and
s'  s
then
s  s s, s  S
e.g., let 
than”
: “older
if Sam is older than Bill,
then Bill cannot be older
than Sam
Properties of PO
– Transitive
If
s  s'
and
s  s
then
s  s
e.g., If the Redskins beat the Patriots
and the Patriots beat the Cowboys
then the Redskins will beat the Cowboys
Total Ordering
• aka
– Chain, simply ordered set, totally ordered set
• A Partial Ordering for Which All Orderings
Are Specified
• A Chain Is “Connected” Because
s  s or s  s s, s S
POSET
• Partially Ordered SET
– A set on which a partial ordering is specified
– ( S,  ) where  is defined
– Not a chain since not all elements are
connected
• We Will Revisit This Concept in a later part
of the Course
Finite Automata
A Deterministic semi-automaton*, aka
Completely Specified Deterministic Semiautomaton Is a Triple
M   S, I,  , or
M   K , Σ,  
with no Mealy machine output function,
Beta ()
* Ginzburg, 1968
FSM Set Properties
S  K   s0 , s1 , s2 , , sn 1  A finit eset of states
I     i0 , i1 , i2 , , im 1   A finit eset of inputs
  S  I  S     S  I , S

    sa , ib , sc  ,   sd , ie  , s f ,   sg , ih , si , 

S
sa
sc
I
ib

Language Recognizer
• aka, Rabin-Scott Automata (machine),
Automaton, Language Recognizer
• A Recognizer Is a Quintuple of Sets
M rs   S, I, , s0 , F

with S, I,  as before
s0  the single, unique, initial state


F  sp , sq ,  A finite set of final states  S
Kleene Star
• a* = e, a, aa, aaa, aaaa, ...
• The Kleene Star, *, means NONE or more
occurrences of something
• Star is an overloaded operator so be aware of
context
• a+= ONE or more occurrences of something.
• a+ is Kleene Star less the null string, .
Kleene Closure
• Kleene Closure Is Not Identical to Kleene
Star
– “*” Symbol is the same (overloaded)
• Kleene Closure/Star Closure
– Found in descriptions of formal language
– Language consisting of all strings over some
alphabet
String
• An Ordered Concatenation of Symbols
From an Alphabet
• Used in Place of “Word” to Decouple From
Common Concept of Word in Informal
Language
• If  = { a, 1, 0, b, % } then a “1%0b” is a
string.
Recognizer
If x  I*,
i.e., a string of input symbols selected from
the set of allowable input symbols,
and
the application of x to the recognizer results
in a final state  F,
then
the recognizer “accepts” the string.
Strings
A String, x, Is Accepted by a Recognizer Left-most
Letter First, i.e.,
if
the input to a recognizer is a string w,
and if
w=
w’
then
 is the first letter of the string which causes a state
transition. Subsequent letters from left to right do the
same.
State Transition
Let There Be Two Configurations for a
Machine
q, w  and q' , w'  which are relat edby t herelat ion,R,
M
q, w  
 q ' , w' 

1
iff
 1 w w
for some  
q
S
q’
String Example
Let
w=abba
then
w = a w’
and
w’ = b b a
Recognizer as Directed Graph
• Arbitrary State
q
• State Transition
q
1
• Start (initial) State
-
or
• Final State
+
or
q’
Recognizer Examples
Let I = { a, b }
• Accepts no strings since no final state
a, b
• Accepts all strings
a, b
• Dead State
a, b
-
Recognizer Examples
• Accepts only , the null string
+/-
a,b
a,b
Recognizer Example
This Recognizer Accepts the Language
L= { ab, a (aa) b, a (aa) (aa) b, ...
ab (bb), ab (bb) (bb), ... }
a
a
L = a (aa)* b ( b (aa)* b )*
b
b
Rabin-Scott Example
S   1, 2, 3, 4 
M rs   S, I, , s0 , F
I   a , , ; 

ps\input
1
F4
2
3
4
s0   1 
4
a
2
3
3
3
+
3
1
3
3

;
3
4
3
3
Rabin-Scott Example
L (M) = { x  I* | * ( 1, x ) = 4 }
a
1
2
+
+ ;
;
a
3
a+;
a+;
L (M) = { a; , a+a; , a+a+a; , ... }
4
Non-Deterministic FSM
A Non-deterministic Finite Automata Is a
Quintuple with S, I, s0, F
M nd   S, I, , s0 , F 
as in a recognizer, but,
  S  I *  S     S  I * , S  ,
is a relation,not a function
   sa , xb , sc ,   sd , xe , s f , 


   sd , xe , sg ,   sh ,  , s j , 
Non-Deterministic FSM
• State May Change
– to two different states in response to the same
input at the same state
– in response to a string rather than just a single
element from the set of inputs
– in response to a null string input
DFA-NDFA Theorem
• Every NDFA Can Be Replaced by an
Equivalent DFA
• Equivalent Means Not Only Accepting All
Strings Accepted by the NDFA, but Also
NOT Accepting Any Others
NDFA Example
Non-deterministic Since
( ( 1, a ), 2 ) and ( ( 1, a ), 3 )
a
2
b
b
11
a
3
4
NDFA Example
Non-deterministic Since Not Completely
Specified
L =  ab, abb 
ab
1
abb
4
NDFA Example
Non-deterministic Since State Changes in
Response to a Null String.

a
2
b
1
bb
a
3
4
NDFA to DFA
• Theorem
– For each NDFA there is an equivalent DFA
• Constructive Proof
• 4 Difficulties to Resolve
–
–
–
–
Missing transitions
Single transitions due to | strings | > 1
Transitions due to  strings
Multiple transitions
Problem: Missing Transitions
• I = { a, b }
• In DFA, all i  I must be accounted for in
each state
a
b
?
Solution: Missing Transitions
Add a “sink” state which is not a final state
and terminate all missing transitions there.
a
a, b
b
a, b
Problem: | strings | > 1
• Single transition due to string of size > 1
• Add intermediate states and “sink”, other
characters in those states go to “sink” state
a
b
ab
a
a, b
Problem:  Strings
Can’t just combine states since

a
b

a
b
b
a
b
a
Solution:  Strings & Multiple
Transitions
• Eliminate  by defining the set of next
states which occur in response to no input,
call this function E(  )
• E(  ) is called the “equivalents of (  )
NDFA Example

2
b
a

> 1
b
3
a
4
b
a
State Equivalents
E( 1 ) = {self, explicit alternative} = { 1, 3 }
E( 2 ) = { 2 }
E( 3 ) = { 3 }
E( 4 ) = { 4 }
• Define a new machine based on the old
using the E(  ) states
New Machine
   E1, a ,  2, 3, 4  
   E1, b ,  5  , state 5 is new dead state
   E 2, a ,  5  
   E 2, b ,  3  
   E 3, a ,  3, 4  
   E 3, b ,  5  
   E 4, a ,  5  
   E 4, b ,  E1, 4       E 4, b ,  1, 3, 4  
New Machine Transition Table
Equiv Old New
Input
alent State State
a
E ( 1 ) { 1, 3 } A { 2,3,4 } = F
E(2)
2
B
5=E
E(3)
3
C { 3, 4 } = G
E(4)
4
D
5=E
Input
b
5=E
3=C
5=E
{ E( 1 ), 4 }
{ 1, 3, 4 } = H
New Machine Transition Table
Equiv Old New
Input
Input
alent State State
a
b
E(5)
5
E
5=E
5=E
2, 3, 4 F { 5, 3, 4 } = I { 3, 5, E(1), 4}
{ 1, 3, 4, 5} = J
3, 4
G { 3, 4, 5 } = I { 5, E(1), 4}
{ 1, 3, 4, 5} = J
1, 3, 4 H 2, 3, 4, 5 = L { 5, E(1), 4}
{ 1, 3, 4, 5} = J
New Machine Transition Table
Old
State
3, 4, 5
New
State
I
1, 3, 4, 5
J
2, 3, 4, 5
L
Input
a
{ 3, 4, 5 } = I
Input
b
{ 5, E(1), 4}
{ 1, 3, 4, 5} = J
{ 2, 3, 4, 5 }= L { 5, E(1), 4}
{ 1, 3, 4, 5} = J
{ 5, 3, 4 } = I { 3, 5, 4, E(1) }
{ 1, 3, 4, 5} = J
DFA Equivalent of NDFA
Reduced DFA Equivalent