School of Computing and Information Systems The University of Melbourne COMP90042
NATURAL LANGUAGE PROCESSING (Semester 1, 2021)
Workshop exercises: Week 8
Discussion
1. What are regular grammar and regular language? How are they different?
(a) Regular languages are closed under union, intersection and concatenation. What does it mean? Why is it important?
(b) Draw a Finite State Acceptor (FSA) for word morphology to show the possi- ble derivations from root forms using the words: play, played, playing; walk, walked, walking; sit, sat, sitting.
(c) What are Weighted Finite State Acceptors (WFSAs)? When and why are they useful?
2. What is parsing?
3. Consider the following simple context–free grammar:
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> “saw” | “walked”
NP -> “John” | “Bob” | Det N | Det N PP
Det -> “a” | “an” | “the” | “my”
N -> “man” | “cat” | “telescope” | “park”
P -> “on” | “by” | “with”
(a) What changes need to be made to the grammar to make it suitable for CYK parsing?
(b) Using the CYK strategy and the above grammar in CNF, parse the following sentences:
i. “a man saw John”
ii. “an park by Bob walked an park with Bob”
iii. “park by the cat with my telescope”
• This sentence has no parse, because the cell [0,7] doesn’t have an S.
1