Parsing and Generation

Question 1

Generative Grammar

Answer 1

A formally specified grammar that can generate all and only the acceptable sentences of a natural language.

Question 2

Constituent

Answer 2

Something that is enclosed in a pair of brackets

Question 3

Weakly-equivalent grammars

Answer 3

Generate the same strings.

Question 4

Strongly-equivalent grammars

Answer 4

Assign the same bracketings to all strings they generate.

Question 5

Context-Free Grammars

Answer 5

Four components:

1. A set of non-terminal symbols conventionally written in uppercase.
2. A set of terminal symbols, conventially written in lowercase.
3. A set of rules, where the left hand side is a single non-terminal and the right hand side is a sequence of one or more non-terminals or terminals.
4. a start symbol, congenitally S, which is a member of the set of non-terminal symbols

Question 6

Empty Productions

Answer 6

Productions with an empty righthand side. Convenient to exclude these as they complicate parsing algorithms and a weakly-equivalent grammar can be constructed that disallows such empty productions.

Question 7

Left-associative

Answer 7

A grammar in which all nonterminal daughters are the leftmost daughter in a rule.

Question 8

Right-association

Answer 8

A grammar where all the nonterminals are rightmost is right-associative.

Question 9

Lexical Ambiguity

Answer 9

Ambiguity arising from dual lexical entries of words e.g. words that can be treated as different types of verbs or as a verb or noun. They can fish is a classic example.

Question 10

Structural Ambiguity

Answer 10

Ambiguity arising from different possible attachments of phrases.

Question 11

Parse tree

Answer 11

Structure of sentence in the form of a tree. Equivalent to bracketed structure but easier to read for complex cases.

Question 12

Chart Parsing

Answer 12

Keeping a record of rules that we’ve applied so we don’t have to back track and redo work that we’ve done before. This works for parsing with CFGs because the rules are independent of context. The data structure used for recording partial results is known as a chart. Such strategies are designed to be complete. See pages 31-35 for more details.

Question 13

Packing

Answer 13

Changing the daughters value on an edge to be a set of lists of daughters and to make an equality check before adding an edge so we don’t add one that’s equivalent to an existing one.

Question 14

Why can’t FSAs be used to model natural language syntax?

Answer 14

Centre embedding which is present in natural language is not possible with FSAs however they may only have finite levels of embedding which means FSAs may suffice. However, grammars written using finite state techniques alone are highly redundant and without internal structure, we can’t build up good semantic representations.

Question 15

Deficiencies in Atomic Category CFGs.

Answer 15

If simple don’t account for subject-verb agreement. We could allow for agreement by increasing number of atomic symbols. This approach doesn’t deal with subcategorisation, the lexical property telling us how many arguments a verb can have.