Читать книгу A Companion to Chomsky - Группа авторов - Страница 54

An unrestricted rewriting grammar works with a specified set of nonterminal symbols, and specified set of terminal symbols. One of the nonterminal symbols is designated as the grammar's start symbol. The grammar also specifies a set of rewrite rules of the form where is any non‐empty string of nonterminal and terminal symbols, and is any (possibly empty) string of nonterminal and terminal symbols. A rewrite rule says that from any string that contains , we can derive a new string that is like but has replaced with . We say that a rewriting grammar generates a string if can be derived from the grammar's start symbol via a sequence of steps using the grammar's rewrite rules, and contains only terminal symbols.

It turns out that grammars of this sort are extremely powerful – in fact, they are general purpose computing devices, capable of carrying out any computation that a Turing machine is capable of.⁷ For example, the grammar in Figure 5.1,⁸ emulates a machine that begins with the length‐one string a, and “doubles” this string repeatedly to produce aa, then aaaa, then aaaaaaaa, before stopping at some point with the current string as output. I use uppercase letters for nonterminal symbols and letters in a different font for terminal symbols. So in the grammar in Figure 5.1, the set of nonterminal symbols is , and the set of terminal symbols is {a}. The empty string is written as .

For any string that we choose, the grammar in Figure 5.1 generates if and only if the length of is a power of two and no symbol other than a occurs in . For convenience we sometimes say, using “generate” in a subtly different sense, that the grammar generates the set of strings that satisfy these conditions. A set of strings is sometimes called a “stringset”.⁹ Thus the grammar in Figure 5.1 generates the stringset .

Figure 5.1 The nonterminal symbols L and R mark the left and right edge of the string. We begin with one occurrence of a between these markers; the nonterminal symbols F and B serve as a device that doubles this inner string to form aa, then aaaa, etc., arbitrarily many times. On each single “doubling cycle” of this device, F moves forward through the string replacing each occurrence of a with two (rule ii), and then B moves backward (rule iv) until it reaches the left edge. At the end of any such cycle, B can be replaced (rule vi) by the “cleaning up” symbol X, which deletes the left edge marker (rule vii), then moves rightward through the string (rule viii) to eventually delete the right edge marker (rule ix)

Note that there is no direct connection between the notion of generation and that of sets: a grammar generates a set only by virtue of generating (all and only) the strings contained in it. While it is convenient to talk of “generating a set of strings,” fundamentally it is strings that are generated, not sets – similarly, while it is convenient to talk of “eating a pile of apples,” it is apples that are eaten, not piles.