A Companion to Chomsky. Группа авторов

A Companion to Chomsky

Grammars

We begin with the general concept of a string‐rewriting grammar, which provides the setting in which the Chomsky hierarchy can be formulated.

5.2.1 Unrestricted Rewriting Grammars

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

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.

5.2.2 Restrictions on Grammars

There are (at least) two reasons why we might question the usefulness of unrestricted rewriting grammars in our theories of natural language.

An obvious one, perhaps, is that since they can carry out any computational procedure at all, adopting this class of grammars would not constitute a meaningful hypothesis about what is a possible human language. This is an objection on the grounds of the generative capacity of the formalism.

The concern that is more prominent in Chomsky's early discussions, however, involves the notion of a structural description. This concern is not about the range of possible grammars made available by the formalism, but about what is said by the fact that a particular grammar generates a particular string. The idea is that if a grammar generates a sentence , then we would like to be able to identify “a structural description of (with respect to the grammar ) giving certain information which will facilitate and serve as the basis for an account of how is used and understood by speakers of the language whose grammar is ; i.e., which will indicate whether is ambiguous, to what other sentences it is structurally similar, etc.” (Chomsky, 1959, p. 138). Chomsky's chosen way to make this notion precise was to import the existing idea of “immediate constituent analysis” (Harris, 1946, 1954; Wells, 1947) and take trees of the now‐familiar sort to be the desired kind of structural descriptions (Chomsky, 1959, p. 141).¹⁰ But there is no obvious way to associate a derivation in

Скачать книгу