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

1 1 Thanks to Bob Frank, Bruce Hayes, Jeff Heinz, Norbert Hornstein, Kyle Johnson, Paul Pietroski, and the editors and reviewers for helpful comments and suggestions on earlier drafts.

2 2 Chomsky (1956), Chomsky and Miller (1958), Chomsky (1959, 1963), Chomsky and Miller (1963), Miller and Chomsky (1963).

3 3 For standard presentations from the general perspective of the theory of computation, see e.g. Hopcroft and Ullman (1979), Lewis and Papadimitriou (1981) and Sipser (1997). For more linguistics‐oriented presentations, see e.g. Levelt (1974), Partee et al. (1990).

4 4 For generalizations beyond the case of strings as the generated objects, see the rich literature on tree grammars (e.g. Thatcher, 1967, 1973; Thatcher and Wright, 1968; Rounds, 1970; Rogers 1997; Comon et al. 2007). Generalizations beyond binary grammaticality arise via the theory of semirings (e.g. Kuich 1997; Goodman 1999; Mohri 2002).

5 5 Notice that the argument here does not concern the usefulness of the traditional notion of weak generative capacity that emerges from the original work on the Chomsky hierarchy, or the viewpoint which equates natural languages with sets of strings and asks where those sets of strings fall on the hierarchy (or extensions of it). The main point I hope to make here is that the usefulness of the Chomsky hierarchy for theoretical linguistics need not be limited to what emerges from those traditional and better‐known perspectives.

6 6 See e.g. Carnie (2013, pp. 48–50), Fromkin et al. (2000, pp. 147–151). Johnson (2019) gives a particularly clear presentation of the fundamental relationship between substitution classes and phrase structure.

7 7 See e.g. Chomsky (1963, pp. 358–359), Levelt (1974, pp. 106–109), Partee et al. (1990, pp. 516–517), Hopcroft and Ullman (1979, pp. 221–223).

8 8 This is based on an example from Hopcroft and Ullman (1979, pp. 220–221).

9 9 Much of the technical literature uses the term “language” here, but this creates unnecessary distractions.

10 10 See also Chomsky, 1956, Section 3.1; Chomsky and Miller, 1963, pp. 288–289.

11 11 The phrase structure grammars considered in section 3 of Chomsky (1956) do not correspond exactly to any of the classes in (1) that are discussed in Chomsky (1959).

12 12 Citing Harris, 1951, Chomsky (2006, p. 172, fn.15) writes that “The concept of ‘phrase structure grammar’ was explicitly designed to express the richest system that could reasonably be expected to result from the application of Harris‐type procedures to a corpus.”

13 13 Hopcroft and Ullman (1979, p. 224) show that this stringset can be generated by a grammar consisting of rules where is at least as long as . The stringsets generable by grammars satisfying this “non‐contracting” requirement are the same as those generable by Type 1 grammars (Chomsky, 1959, pp. 144–145). The non‐contracting requirement is sometimes given as an alternative condition defining Type 1 grammars, e.g. Levelt (1974, pp. 27–29). Chomsky (1963, pp. 360–363), departing from the Chomsky, 1959 numbering system that has now become standard, defines Type 1 grammars with the non‐contracting requirement, and calls grammars with rules satisfying the format “Type 2 grammars.”

14 14 This is the Myhill‐Nerode Theorem (e.g. Hopcroft and Ullman, 1979, p. 65).

15 15 This logic is the basis of the CKY algorithm, due to Cocke and Schwartz (1970), Kasami (1965) and Younger (1967); see also Hopcroft and Ullman (1979, pp. 139–141).

16 16 “I do not know whether English is actually a terminal language or whether there are other actual languages that are literally beyond the bounds of phrase structure description. Hence I see no way to disqualify this theory of linguistic structure on the basis of [generative capacity]. When we turn to the question of the complexity of description …, however, we find that there are ample grounds for the conclusion that this theory of linguistic structure is fundamentally inadequate.” (Chomsky, 1956, Section 4). See also Chomsky and Miller (1963, p. 297).

17 17 This follows from the relationship between CSGs and linear bounded automata; see e.g. Hopcroft and Ullman (1979, p. 225).

18 18 I am leaving aside here the issues raised by rules like XZ XYZ, which, because they satisfy Restriction 1 “in two ways,” do not let us uniquely identify a tree structure for each derivation; and therefore do not even let us say which strings are derived from which nonterminal symbols in any sense. This can be overcome by simply requiring that such rules be reformulated as either “X XY / _ Z' or ‘Z YZ / X _.” For other discussions of the relationship between Type 1 grammars and tree structures, see Partee et al. (1990, pp. 448–450) and Levelt (1974, pp. 29–31).

19 19 This is closely analogous to the point made by the wrap operation introduced by Bach (1979), modulo the distinction between raising and control.

20 20 Chomsky (1956, Section 4.1) briefly mentions that the move from CFGs to transformational grammars introduces the possibility of “selecting as elements certain discontinuous strings,” for example (has,‐en) and (be,‐ing). But this perspective on transformational grammars seems to have not been discussed much otherwise.