Problem of the Month
Problem 2: Manuals for Robots

A course for a robot is a finite set of places (denoted by circles or squares) with arrows labelled \(a\) and \(b\) between places, satisfying the following conditions:

1. For every place \(s\), there is exactly one arrow labelled \(a\) and one arrow labelled \(b\) which starts at \(s\).

2. There is exactly one place called the starting place, denoted by a square.

3. Some positive number of places are called finishing places, and they are denoted by being shaded. The starting place can be a finishing place.

4. The course is connected. That is, there is a way to get from the starting place to any other place by following (possibly several) arrows.

While there is exactly one arrow labelled \(a\) and one arrow labelled \(b\) starting at every place, there may be multiple arrows labelled \(a\) ending at a particular place, or none at all! Take a moment to check that the following three examples are indeed courses.

For a particular course, we can give a robot instructions as to how to move from place to place in the form of a string. A string is a finite sequence of \(a\)'s and \(b\)'s (for example, \(abaa\)).

For each string, the robot begins at the starting place, and follows the arrows in the order they appear in the string (reading from left to right), moving from place to place.

If the robot ends at a finishing place, then the string is accepted. Otherwise, the string is rejected. Notice that by Condition \(1\) in the definition of a course, the string completely determines which places the robot visits.

The set of accepted strings is the manual for that course. For example, the manual for Course 3 above is the set of all strings. Convince yourself that the manual for Course 1 is the set of strings with an odd number of \(b\)'s.

1. Decide which of the following strings belong to the manual for Course 2 from the first page: \(abb\), \(aab\), \(baaaa\), \(abba\).

2. Describe the manuals for the following courses:

   1. 
      
      Hide/Reveal Description of Course for 2(a)
      • There are three places, arranged in a row. From left to right, there is an unshaded square, a shaded circle, and an unshaded circle.
      • There are six arrows:
        • Starting at the unshaded square, the arrow labelled \(a\) ends at the shaded circle, and the arrow labelled \(b\) loops around and ends at the unshaded square.
        • Starting at the shaded circle, the arrow labelled \(a\) ends at the unshaded circle, and the arrow labelled \(b\) loops around and ends at the shaded circle.
        • Starting at the unshaded circle, the arrow labelled \(a\) loops around and ends at the unshaded circle, and the arrow labelled \(b\) loops around and ends at the unshaded circle.

      ---

   2. 
      
      Hide/Reveal Description of Course for 2(b)
      • There are four places arranged into a 2 by 2 grid. An unshaded square is top left, a shaded circle is top right, and two unshaded circles are bottom left and right.
      • There are eight arrows:
        • Starting at the unshaded square, the arrow labelled \(a\) ends at the shaded circle, and the arrow labelled \(b\) ends at the bottom-left unshaded circle.
        • Starting at the shaded circle, the arrow labelled \(a\) loops around and ends at the shaded circle, and the arrow labelled \(b\) ends at the bottom-right unshaded circle.
        • Starting at the bottom-left unshaded circle, the arrow labelled \(a\) ends at the bottom-right unshaded circle, and the arrow labelled \(b\) ends at the unshaded square.
        • Starting at the bottom-right unshaded circle, the arrow labelled \(a\) loops around and ends at the bottom-right unshaded circle, and the arrow labelled \(b\) ends at the shaded circle.

      ---

3. 1. Construct a course whose manual is the set of three strings \(\{a,ab,bbb\}\).

   2. Construct a course whose manual is the set of all strings where the number of \(a\)'s in the string is a multiple of \(3\).

4. For this problem we need to introduce some language and notation.

   The length of a string is the number of characters in the string. For example, \(aaba\) has length \(4\). The string of length \(0\) is called the empty string and we denote it by \(e\).

   If \(x\) and \(y\) are strings, then \(xy\) is the concatenation of the two strings. The string \(x^n\) is \(x\) concatonated with itself \(n\) times. For example, if \(x = bab\), \(y = ba\), and \(z = aab\), then \(xy^3z = babbababaaab\). Define \(x^0\) to be the empty string \(e\).

   A substring of a string \(x\) is a string consisting of consecutive letters from \(x\). For example, \(ab\), \(ba\), \(e\), and \(baba\) are all substrings of \(baba\). The string \(bba\) is not a substring of \(baba\).

   1. Suppose a course has \(k\) places, and let \(w\) be a string in its manual of length at least \(k\). Show that there is a substring \(y\) of \(w\) with length at least \(1\) and at most \(k\) so that when it is deleted from \(w\), the remaining word is also in the manual.

   2. Suppose a course has \(k\) places, and let \(w\) be a string in its manual of length at least \(k\). Show that you can write \(w = xyz\) with the property that \(y \neq e\), the length of \(y\) is at most \(k\), and for all natural numbers \(n\), \(xy^nz\) is also in the manual.

   3. Prove that the manual for a course cannot be the set of all strings with length equal to a perfect square.

   4. Prove that the manual for a course cannot be the set of all strings that are palindromes. (A palindrome is a string that is the same when written backwards. The strings \(abba\) and \(aaa\) are palindromes, but \(ba\) is not.)