Parsing and Generation

Question 1

What are the main points to be made about chart-parsing?

Answer 1

-A chart is a data structure used in a family of algorithms for parsing natural language.
-It allows dynamic programming by storing the partial results of parsing, thus avoiding
the need for recomputation.
- Numbers are associated with the text which is input to parsing so the span of rule
applications can be recorded.
- Describe the fields of each edge.

Question 2

Why can’t FSAs model the syntax of natural language?

Answer 2

• Centre embedding, i.e grammars of the form
  A -> aAb cannot be accepted by FSAs, because they are not REGULAR. (Although in reality natural language only has a limited amount of embedding).
• FSAs are highly redundant making them difficult to maintain and disallowing an effective semanic model to be built.

Question 3

What are the deficiencies in CFGs?

Answer 3

• No subject-verb agreement
• No support for subcategorisation (the fact that verbs take different numbers of objects as arguments).
• No support for long distance dependencies, e.g “which kids did you say were making all that noise?”