tutorial7.dvi
COMP9414: Artificial Intelligence
Tutorial 7: Language Processing
1. Trace the bottom up chart parsing algorithm using the following grammar and lexicon to
parse the sentence “0 This 1 is 2 the 3 house 4 that 5 Jack 6 built 7 ”. Number the rules and
lexical entries for convenience.
1. S → NP VP 1. this: PRO
2. NP → PRO 2. is: VERB
3. NP → ART NOUN 3. the: ART
4. NP → NAME 4. house: NOUN
5. NP → NP REL S 5. that: PRO, REL
6. VP → VERB 6. Jack: NAME
7. VP → VERB NP 7. built: VERB
2. Consider the conjunction construction in English. Conjunction involves conjoining phrases
and clauses with the connectives ‘and’, ‘or’, ‘but’, ‘if’, ‘so’, ‘although’, ‘because’, etc. This
question focuses on the use of ‘and’.
(i) Write context free grammar rules to accept the following sentences that use ‘and’.
Today is hot and humid.
John and Mary went to the beach.
John went to the park and Mary went to the beach.
John went to the park and had lunch.
John went to the park and to the beach.
John talks quickly and in a loud voice.
(ii) Your grammar will probably overgenerate. Show this by giving examples of nonsen-
tences generated by your grammar.
Augment the grammatical categories with syntactic features to rule out these sentences.
Consider person, number, gender and case agreement.
(iii) Write semantic rules to compute a meaning representation for conjunctive sentences.
(iv) Consider the English conjunction ‘but’. Are there any syntactic, semantic or pragmatic
differences between ‘but’ and ‘and’?