This assignment is due Wednesday, October 13 at 11:59PM.

  1. Goals
  2. Background
  3. Converting a Grammar to Chomsky Normal Form
  4. Requirements
  5. Files

1. Goals

Through this assignment you will:

[back to top]

2. Background

Please review the class slides and readings in the textbook on Chomsky Normal Form conversion.

[back to top]

3. Converting a Grammar to Chomsky Normal Form

As noted in the text, the CKY algorithm requires a grammar in Chomsky Normal Form (CNF). While it is not always intuitively clear how to write a grammar from scratch in CNF, it is fairly straightforward to convert a context-free grammar into a weakly equivalent grammar in CNF.

Following the approach outlined in class, implement a procedure to convert an input grammar of the form to be used for the first assignment to a new weakly equivalent grammar in CNF.

You will want to create data structures corresponding to RULE, RHS, LHS, etc. You may use existing implementations of these data structures in NLTK or other NLP toolkits (e.g. the Stanford Parser), but you must implement the grammar conversion algorithm yourself.

[back to top]

4. Requirements

The program you submit should do the following:

  1. Read in an original context-free grammar.
  2. Convert this grammar to Chomsky Normal Form.
  3. Print out the rules of the converted grammar to a file.

[back to top]

Programming

Create a program named hw2_tocnf to perform the conversion described above. Your program should be able to be invoked with:

hw2_tocnf.sh <input_grammar_file> <output_grammar_file>

where

Verification & Parse Comparison

Using your system from HW#1, you will parse a set of sentences with

NOTE: You will need to run your code yourself in both these conditions with the files specified below. You will include the output parse files in your submission tar file. You do not need to run this code as part of your condor file.

[back to top]

5. Files:

In the Dropbox

You will find the following files in /dropbox/21-22/571/hw2:

Submission Files