A Companion to Chomsky. Группа авторов
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.
References
1 Anne Abeillé and Owen Rambow. 2000. Tree Adjoining Grammars. Stanford, CA, CSLI Publications.
2 Emmon Bach. Control in Montague Grammar. 1979. Linguistic Inquiry 10 (4):515–531.
3 Joan Bresnan, Ronald M. Kaplan, Stanley Peters, and Annie Zaenen. 1982. Cross‐serial Dependencies in Dutch. Linguistic Inquiry 13 (4):613–635.
4 Andrew Carnie. 2013. Syntax: A Generative Introduction. Malden, MA: third edition, Wiley‐Blackwell.
5 Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on Information Theory 2 (3):113–124.
6 Noam Chomsky. 1957. Syntactic Structures. Mouton, The Hague.
7 Noam Chomsky. 1959. On certain formal properties of grammars. Information and Control 2:137–167.
8 Noam Chomsky. 1963. Formal properties of grammars. In R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of Mathematical Psychology, volume 2, pages 323–418. John Wiley and Sons, Inc., New York and London.
9 Noam Chomsky. 1965. Aspects of the Theory of Syntax. MIT Press, Cambridge, MA.
10 Noam Chomsky. 2006. Language and Mind. Cambridge University Press, 3rd edition.
11 Noam Chomsky and George Miller. 1963. Introduction to the formal analysis of natural languages. In R. Duncan Luce, Robert R. Bush, and Eugene Galanter, editors, Handbook of Mathematical Psychology, volume 2, pages 269–321. John Wiley and Sons, Inc., New York and London.
12 Noam Chomsky and George A. Miller. 1958. Finite state languages. Information and Control 1 (2):91–112,
13 Alexander Clark. 2013. The syntactic concept lattice: Another algebraic theory of the context‐free languages? Journal of Logic and Computation 25 (4):1203–1229.
14 Alexander Clark. 2014. An introduction to multiple context‐free grammars for linguists. https://alexc17.github.io/papers/mcfgsforlinguists.pdf .
15 Alexander Clark and Ryo Yoshinaka. 2016. Distributional learning of context‐free and multiple context‐free grammars. In Jeffrey Heinz and José M. Sempere, editors, Topics in Grammatical Inference, pages 143–172. Springer.
16 John Cocke and J. T. Schwartz. 1970. Programming languages and their compilers. Courant Institute of Mathematical Sciences, New York University.
17 H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. 2007. Tree automata: Techniques and applications. Available from: http://www.grappa.univ-lille3.fr/tata. Release October, 12th 2007.
18 Robert Frank. 2002. Phrase Structure Composition and Syntactic Dependencies. MIT Press, Cambridge, MA.
19 Robert Frank. 2004. Restricting grammatical complexity. Cognitive Science 28 (5).
20 Victoria Fromkin, Susan Curtiss, Bruce P. Hayes, Nina Hyams, Patricia A. Keating, Hilda Koopman, Pamela Munro, Dominique Sportiche, Edward P. Stabler, Donca Steriade, Tim Stowell, and Anna Szabolsci. 2000. Linguistics: An Introduction to Linguistic Theory. Blackwell.
21 Joshua T. Goodman. 1999. Semiring parsing. Computational Linguistics 25 (4): 573–605.
22 Zellig S. Harris. 1946. From morpheme to utterance. Language 22 (3):161–183.
23 Zellig S. Harris. 1951. Methods in Structural Linguistics. University of Chicago Press.
24 Zellig S. Harris. 1954. Distributional structure. Word 10 (2–3):146–162.
25 John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison Wesley, Reading, MA.
26 Riny Huybregts. 1976. Overlapping dependencies in dutch. In Utrecht Working Papers in Linguistics, number 1, pages 24–65.
27 Riny Huybregts. 1984. The weak inadequacy of context‐free phrase structure grammars. In Ger J. de Haan, Mieke Trommelen, and Wim Zonneveld, editors, Van Periferie Naar Kern, pages 81–99. Foris, Dordrecht.
28 Gerhard Jäger and James Rogers. 2012. Formal language theory: refining the Chomsky hierarchy. Philosophical Transaction of the Royal Society B 367: 1956–1970.
29 Kyle Johnson. 2019. Transformational grammar. Unpublished course notes.
30 Aravind Joshi. 1985. How much context‐sensitivity is necessary for characterizing structural descriptions? In David Dowty, Lauri Karttunen, and Arnold Zwicky, editors, Natural Language Processing: Theoretical, Computational and Psychological Perspectives, pages 206–250. Cambridge University Press, New York.
31 Aravind K. Joshi, Leon S. Levy, and Masako Takahashi. 1975. Tree adjunct grammars. Journal of Computer and System Sciences 10:136–163.
32 Aravind K. Joshi, K. Vijay Shanker, and David Weir. 1990. The convergence of mildly context‐sensitive grammar formalisms. University of Pennsylvania Department of Computer and Information Science Technical Report No. MS‐CIS‐90‐01.
33 Laura Kallmeyer. 2010. Parsing Beyond Context‐Free Grammars. Springer‐Verlag, Berlin Heidelberg.
34 Tadao Kasami. 1965. An efficient recognition and syntax‐analysis algorithm for context‐free languages. AFCRL Technical Report 65‐758.
35 Werner Kuich. 1997. Semirings and formal power series: their relevance to formal languages and automata. In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages, volume 1, pages 609–677. Springer.
36 Willem J. M. Levelt. 1974. An Introduction to the Theory of Formal Languages and Automata, volume 1 of Formal Grammars in Linguistics and Psycholinguistics. Mouton.
37 Harry