A sequential substitution system is a substitution system in which a string is scanned from left to right for the first occurrence of the first rule pattern. If the pattern is found, the rule is applied and processing advances to the next step. If the first rule pattern does not occur, the string is scanned from left to right for the first occurrence of the second rule pattern. If the pattern is found, the rule is applied and processing advances to the next step, and so on. If none of the rule patterns match at some step, the string repeats indefinitely for all subsequent steps. For example, consider the single rule A->B and the initial string A B A, illustrated above. The first step yields B B A, the second step yields B B B, and from there on the system repeats since there are no more matches of the pattern rule. A more interesting sequential substitution system is illustrated above. This system has two rules (A B A->A A B, A->A B A) and the initial condition B A B A. It builds increasingly long runs of sequential As followed by sequential Bs by temporarily taking away one A before adding two more at the last step of each cycle. In systems with two or more rules, it is possible for some parts of a string to never be replaced as a result of another substitution always occurring first in a left-to-right scan. For example, consider the rules (A B->B A, B->A B) and the initial string A B A B. The first step yields B A A B by replacing the first A B. The second step yields A B A A B by replacing the first B. The third step yields B A A A B by replacing the first A B, and so on. This sequential substitution system will never replace the rightmost A B because it will always be preceded by either B or A B. As a result, it builds ever longer trailing strings of As.

multiway system | substitution system