For Exercises 52–62, refer to the following. Call a sequence musical if repeatedly applying deflation to it eventually results in a single .

Question 20.89

59. We show how to check whether a finite block of s and s can be a part (subsequence) of some musical sequence or else is never a part of any musical sequence. We do so by deflating the block: If the deflation arrives at a single symbol, the block is part of a musical sequence; if the deflation cannot arrive at a single symbol, the block is not part of any musical sequence. However, we use a slightly modified form of deflation:

  • If at any stage of the deflation of the block we arrive at as the starting symbol, we can tack on an initial in front of it (because as an internal part of a musical sequence, the deflated block would have to have an preceding the —it can’t have two Ss in a row and be musical).
  • We add the rule that if at any stage of the deflation of the block we arrive at as the ending symbols, we replace the with (because as an internal part of a musical sequence, the deflated block would have to be followed by an —it can’t have three s in a row and be musical; at the next deflation, the would become .)

    864

  • If, at any stage of this modified deflation, we arrive at two or more s in a row or three or more s in a row, then the original block could not be part of a musical sequence. Otherwise, the original block will deflate eventually to a single symbol, at which point we conclude that the original block is a part of a musical sequence.

Check the two blocks below. Is either a part of a musical sequence?

59.

(a) Yes

(b) No