CSCI 4602
Fall 2000
Homework assignment 1.
A finite state machine is defined to be a 5-tuple
(Q,A,d,q0,F), where Q is the set of states,
A is the alphabet, d is the transition function,
q0 is the start state and F is the set
of accepting states. (I am calling the transition function
d here, to avoid using greek letters.)
Function d* is defined as follows. I use e for the empty string.
d*(q,e) = q
d*(q,xc) = d(d*(q,x),c) (for any string x and single character c)
Exercise: prove that d*(q,xy) = d*(d*(q,x),y) for any strings
x and y over alphabet A.
Hint: Reason by contradiction, and consider the smallest
counterexample. (It suffices to choose x as small as possible.)
Keep in mind that anything smaller than the smallest counterexample
is not a counterexample. Use the definition of d*. Also,
don't lose track of your intuition. Check that your proof
makes sense.