Here the physical setting is a string of formal symbols, which we will commonly take to be letters a, b, c. The rules for evolving a string take the form of rewriting substrings or single letters by replacement strings. These are called rewriting rules.
As a particular example, let's suppose there are exactly two symbols a and b and two rewriting rules:
and
We start at Generation 0 with the string b. By the second rule, Generation 1 is ba, and after that Generation 2 is baaa.
Below is what happens for a few generations.
| Gen. | String |
| 0 | b |
| 1 | ba |
| 2 | baaa |
| 3 | baaaaaaa |
| 4 | baaaaaaaaaaaaaaa |
After a few generations we get the idea that the long-term nature of the string is a single b followed by a lot of a's. Can you determine a formula for the number of a's?