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

---

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

---

answer is that while a FSG is limited to classifying strings according to their role as prefixes (i.e. according to what can come after them), a CFG is able to classify strings according to their role as infixes (i.e. according to what can come around them). The CFG in (2) does not work by specifying what can come after aa, and what can come after aaa, etc.; as we have seen, any finite device that adopts this strategy is doomed. Instead, this grammar works by specifying what can appear around certain strings, and the crucial point is that what can appear around, say, aabb, is the same as what can appear around aaabbb – so while the pattern does not create any interesting equivalences between prefixes, it does create interesting equivalences between infixes. The grammar in (2) takes advantage of this by making a two‐way distinction between (i) strings of the form , which can be combined with any surroundings of the form , and (ii) all other strings. It uses the nonterminal symbol S as a book‐keeping symbol to identify strings belonging to the first class, just as FSGs use states.

      To see these concepts in a more familiar form, consider the CFG in (4). A few example derivations are illustrated with tree diagrams in (5). The stringset that this grammar generates also cannot be generated by any FSG: among strings of the form , only those where there is exactly one occurrence of chase for each occurrence of dogs after the first one will be generated (i.e. those of the form ), so there are unboundedly many nonequivalent prefixes of the form . The early rejection of FSGs as models of natural language was based on the claim that a grammar of English would need to generate patterns of essentially this sort (Chomsky, 1956, §2.3).

      1 (4) start symbol: SSNP VPNdogsNPNAchasedNPA NAbigNPN RCVchasedRCNP VVchaseVPV NPVPsleep

      1 (5)

Subsets of the set of nonterminals characterize classes of strings, grouped according to the ways they can appear as infixes. I will call these sets inside sets: for example, the inside set of the string chase big dogs is , and the inside set of chased dogs is ; see Table 5.5. This partitioning of strings is the CFG's analog of an FSG's partitioning of strings by forward sets, and corresponds to the familiar notion of categorized constituents. A typical motivation for writing a grammar where a single nonterminal can derive, say, both sleep and chase dogs, is to express the idea that they are intersubstitutable infixes, i.e. for any two strings and , if is generated then is also generated. This is the sense in which CFGs carry over earlier ideas from immediate constituent analysis (e.g. Harris, 1946, 1954; Wells, 1947). For more recent discussions of this important notion, see Clark (2013), Clark and Yoshinaka (2016) and Stabler (2019, Section 2).

Table 5.5 Equivalence classes induced by the grammar in (4)

Inside set	Example strings from the corresponding equivalence class
	dogs sleep
	dogs dogs chase sleep
	chased dogs chase dogs
	dogs chased dogs
	dogs
	big dogs
	dogs dogs chase
	dogs dogs dogs chase chase
	sleep
	chase dogs
	chased dogs dogs chase
	chased big dogs
	dogs chase
	dogs chased
	big dogs chased
	dogs
	big
	Скачать книгу