Context-Free Grammars and Constituency Parsing

19.2 Context-free grammars

1. What are other names for context-free grammars, and who formalized them?
   Phrase-structure grammars; the formalism is equivalent to Backus-Naur form (BNF). The idea of constituent structure goes back to Wundt (1900); it was formalized by Chomsky (1956) and independently by Backus (1959).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 426
2. What does a context-free grammar consist of?
   A set of rules (productions) saying how symbols can be grouped and ordered (e.g. NP → Det Nominal, Nominal → Noun | Nominal Noun) and a lexicon of words and symbols (Det → a, Noun → flight).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 426
3. What is the difference between terminal and non-terminal symbols?
   Terminals correspond to words (“the”, “flight”); the lexicon introduces them. Non-terminals are abstractions over terminals (NP, VP, Nominal). A rule has one non-terminal on the left and an ordered list of terminals and non-terminals on the right.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 427
4. What is a derivation, and how is it represented?
   The sequence of rule expansions that produces a string from a non-terminal (NP → Det Nominal → Det Noun → a flight), usually shown as a parse tree with the root at the top.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 427
5. What does it mean that a node dominates or immediately dominates other nodes?
   A node dominates all nodes below it in the tree; it immediately dominates its direct children (NP immediately dominates Det and Nom).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 427
6. What is the language defined by a CFG?
   The set of strings derivable from the designated start symbol, usually S (“sentence”).
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, pp. 427–428
7. Give the main rules of the toy grammar \(L_0\) for English.
   S → NP VP; NP → Pronoun | Proper-Noun | Det Nominal; Nominal → Nominal Noun | Noun; VP → Verb | Verb NP | Verb NP PP | Verb PP; PP → Preposition NP.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, pp. 428–429
8. Draw the parse tree of “I prefer a morning flight” under \(L_0\), in bracketed notation too.
   [S [NP [Pro I]] [VP [V prefer] [NP [Det a] [Nom [Nom [N morning]] [N flight]]]]]

   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 429
9. What are grammatical and ungrammatical sentences with respect to a formal grammar?
   Grammatical sentences can be derived by the grammar (they are in its formal language); ungrammatical ones cannot. This hard in/out line only simplifies natural language, where acceptability often depends on context.
   • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 429
10. What is generative grammar?
    In linguistics, using formal languages to model natural languages: the language is the set of sentences “generated” by the grammar (a different sense of “generate” than LLM text generation).
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 429
11. Give the formal definition of a context-free grammar.
    A 4-tuple \((N, \Sigma, R, S)\): non-terminals \(N\), terminals \(\Sigma\) (disjoint from \(N\)), rules \(R\) of the form \(A \to \beta\) with \(A \in N\) and \(\beta \in (\Sigma \cup N)^*\), and a start symbol \(S \in N\).
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 430
12. Define “directly derives” and the language generated by a grammar.
    If \(A \to \beta \in R\), then \(\alpha A \gamma \Rightarrow \alpha\beta\gamma\). Derivation (\(\Rightarrow^*\)) is a chain of direct derivations, and \(L_G = \{w \mid w \in \Sigma^*, S \Rightarrow^* w\}\).
    • Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 19, §19.2, p. 430