Homework #3 FAQ
May I have a hint on Problem 1?
Yes you may.
Suppose we are constructing the table that tells which pairs of
states are distinguishable.
We immediately put x's for the pr and qr pairs; the only question is
whether we can distinguish p from q.
We could use either input 0 or input 1 to distinguish them.
Let's ask under what conditions 0 lets us put an x in the pq entry?
There are nine possible combinations of values for delta(p,0)
and delta(q,0). For example, if delta(p,0)=r and delta(q,0)=p,
then we can put the x.
If delta(p,0)=q and delta(q,0)=p, then we cannot justify putting the x.
How many of the 9 possibilities let us put the x?
Then, ask the same question for the 1 input, and you'll be able to
answer the question how many of the possible delta's justify the x
in some way.
Note that the transitions from r are irrelevant, since they cannot possibly
be used to justify the x in the pq entry.
How about a hint on Problem 3?
Look at the grammar of Fig. 5.1, which generates palindromes only.
Notice how by spinning the same symbol to the left and right of the one
variable, you get strings to the left of the variable that are the reverse
of the strings to the right of the variable.
If we also allowed mismatching terminals on either side, we would get
strings of the same length on either side, but they might or might not
be the reverse of each other.
The solution to problem 3 lies in figuring out how to add a second variable
to force there to be at least one mismatch of the symbols on either side
of the variable before generating the c and deriving a string