Formal languages [and multiway systems]

The multiway systems that I discuss are similar to so-called generative grammars in the theory of formal languages. The idea of a generative grammar is that all possible expressions in a particular formal language can be produced by applying in all possible ways the set of replacement rules given by the grammar. Thus, for example, the rules {"x"  "xx", "x"  "(x)", "x"  "()"} starting with "x" will generate all expressions that consist of balanced sequences of parentheses. (Final expressions correspond to those without the "non-terminal" symbol x.) The hierarchy described by Noam Chomsky in 1956 distinguishes four kinds of generative grammars (see page 1104):

Regular grammars. The left-hand side of each rule must consist of one non-terminal symbol, and the right-hand side can contain only one non-terminal symbol. An example is {"x"  "xA", "x"  "yB", "y"  "xA"} starting with "x" which generates sequences in which no pair of B's ever appear together. Expressions in regular languages can be recognized by finite automata of the kind discussed on page 957.

Context-free grammars. The left-hand side of each rule must consist of one non-terminal symbol, but the right-hand side can contain several non-terminal symbols. Examples include the parenthesis language mentioned above, {"x"  "AxA", "x"  "B"} starting with "x", and the syntactic definitions of Mathematica and most other modern computer languages. Context-free languages can be recognized by a computer using only memory on a single last-in first-out stack. (See pages 1091 and 1103.)

Context-sensitive grammars. The left-hand side of each rule is no longer than the right, but is otherwise unrestricted. An example is {"Ax"  "AAxx", "xA"  "BAA", "xB"  "Bx"} starting with "AAxBA", which generates expressions of the form Table["A", {n}] <> Table["B", {n}] <> Table["A", {n}].

Unrestricted grammars. Any rules are allowed.

(See also page 944.)