Regular expressions

The sequences in a regular language correspond to those that can be matched by Mathematica patterns that use no explicit pattern names. Thus for example {(0 | 1) ...} corresponds to all possible sequences of 0's and 1's, while {1, 1, (1) ..., 0, (0) ...} ... corresponds to the sequences that can occur after 2 steps in rule 126 and {(0) ..., 1, {0, (0) ..., 1, 1} | {1, (1) ..., 0}} ... to those that can occur after 2 steps in rule 110 (see page 279).