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).