Homework #3 FAQ

Question: May I have a hint on Problem 1?
Answer: 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.

Question: How about a hint on Problem 3?
Answer: 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 of terminals.