Problem

Source: 2004 Estonia National Olympiad Final Round grade 11 p5

Tags: alphabet, combinatorics



The alphabet of language $BAU$ consists of letters $B, A$, and $U$. Independently of the choice of the $BAU$ word of length n from which to start, one can construct all the $BAU$ words with length n using iteratively the following rules: (1) invert the order of the letters in the word; (2) replace two consecutive letters: $BA \to UU, AU \to BB, UB \to AA, UU \to BA, BB \to AU$ or $AA \to UB$. Given that $BBAUABAUUABAUUUABAUUUUABB$ is a $BAU$ word, does $BAU$ have a) the word $BUABUABUABUABAUBAUBAUBAUB$ ? b) the word $ABUABUABUABUAUBAUBAUBAUBA$ ?