Quizz 09: Syntactic Parsing

This quizz covers material from the ninth lecture on Syntactic Parsing.
  1. Show the dependency parse tree of the following English sentence (without labels on the edges):
    The little girl reads a book about NLP.
    







  2. Show the constituency structure of the same sentence - where the pre-terminals (part of speech categories) are Det, Adj, N, V, Prep and the non-terminal categories are NP (noun phrase), VP (verb phrase), PP (prepositional phrase) and S (sentence).









  3. Provide the formal definition of a CFG:

    A CFG is defined by a 4-tuple (NT, T, S, R) where:






  4. When generating random sequences according to a CFG, what are the 2 primitive operations that must be implemented to follow the semantics of the CFG?








  5. What are the possible forms of rules for a CFG in Chomsky Normal Form (CNF)?








  6. What is the complexity of parsing a sentence of n words according to a CFG grammar?










Last modified 30 Dec 2018