Notes

Chapter 5: Two Dimensions and Beyond

Section 7: Systems Based on Constraints


Formal languages [and constraints]

Formal languages of the kind discussed on page 938 can be used to define constraints on 1D sequences. The constraints shown on page 210 correspond to special cases of regular languages (see page 940). For both regular and context-free languages the so-called pumping lemmas imply that if any finite sequences satisfy the constraints, then so must an essentially repetitive infinite sequence.


From Stephen Wolfram: A New Kind of Science [citation]