Natural Language Generation (201-2454101)
Assignment 1 - Spring 1998 - Michael Elhadad

Natural Language Generation - Assignment 1

Random Generation - Limits of Context Free Grammars

The following files implement two solutions to the problem of generating random sentences from a context-free grammar. They serve as the basis for the assignment:
  1. Generate1.l: procedural representation.
  2. Generate2.l: explicit representation of grammars with interpreter.

Question 1

Write an extension of the bigger grammar in generate2.l that limits the depth of the generated tree to 5 levels. In other words, the grammar is finite and can only generate trees of depth up to 5.

Question 2

Write a new interpreter for grammars that receives as an additional parameter the maximum depth of the tree to be generated.

Question 3

Write a new interpreter for grammars that generates exhaustively all the sentences of a grammar in increasing order of tree depth. The interpreter has a parameter n, for the maximum number of sentences to output, and generates all the sentences with depth 1 first, then all the sentences of depth 2, 3... until n sentences have been produced.

Question 4

Write a CFG grammar that can generate sentences with transitive and intransitive verbs appropriately. For example: 
John runs

John buys a pizza.
but not: 
* John runs a pizza.

* John buys.
(Note: The * before a sentence is a convention in linguistics indicating that it is not grammatical.)

Question 5

Write a grammar for Scheme programs with the following constructs:
  1. lambda
  2. function application
  3. +, -, *, /, display
  4. numbers
Give examples of features of well-formed Scheme programs that cannot be modeled by a context-free grammar.

Question 6

Write a grammar for Hebrew with the following features:
  1. Coverage similar to that of *bigger-grammar*
  2. (Prep -> le be al im)
  3. (Adj -> katan gadol cahol tsahov)
  4. (Article -> ha)
  5. (Name -> Avraham Yitzhak Yaakov)
  6. (Noun -> shulhan cise luah iparon)
  7. (Verb -> lakah raa ahav ratz)
  8. (Pronoun -> hu hi ze)
The grammar must work properly with definite and indefinite noun phrases: 
Avraham lakah et ha shulhan ha katan

Avraham lakah shulhan katan

* Avraham lakah et ha shulhan katan

* Avraham lakah et shulhan ha katan

Last modified March 3rd, 1997 Michael Elhadad