In the system, you always start with the string and then form new strings by applying any of following rules any number of times:
Rules | Examples |
1. If your string ends with , you can add a at the end. | |
2. You can double the entire string following | |
3. Three consecutive 's can be replaced with a single | |
4. Two consecutive 's can be removed from the string. |
Which of the following strings can be derived from using these rules?
Note: None of the rules can be used in the opposite way; for example, you aren't allowed to derive from by using a reversed version of rule 4.
Source: The puzzle was introduced by Douglas Hofstadter in his magisterial work Gödel, Escher, Bach.