CS 390 Homework 7
Read
"Equivalence of NFA-
and NFA"
in
8. E. of the Course Materials and answer the following questions.
1. Explain how a proof by induction on strings would proceed to prove a statement P(w)
on string w in {a , b}* , i.e. explain what you do in Basis and Inductive Steps.
2. What are the children of q in
(S 
T) ?
3. In proving
(S T)
(S)
by induction on
(S T),
what do we need to do
in Basis and Inductive Steps ? Why ? You don't need to give details of a proof. Just explain what you do.
Due March 25, 2013, end of the day. No late hand-ins
accepted.
You may discuss these questions among yourselves and/or with me.
But you must write the answers in your own words.