Homework 4

15-212 Java, Spring 1998

February 25, 1998
Instructors: Mosur and Tygar

This assignment is due at start of your section on March 11. Please read the class policies for collaboration, cheating, and late assignments. Answers that are unclear, illegible, rambling, or otherwise annoying will receive no credit. The best answer is the shortest correct answer.

IMPORTANT: Same as always. Put your name, your section, and your email at the top of the first page of each part. Don't hand in part 1, though.

Part I: Not for credit (so don't hand it in)

1. Read section 3.6 in L&P. You may gloss over the proof on pages 155-6.

2. The following grammar in Chomsky normal form generates matched-parenthesis strings:

S	=>	SS \| (S₁ \| ()
S₁	=>	S)

Using the CYK algorithm (the dynamic programming algorithm described in 3.6), determine whether the string (()()) is generated by the grammar.

Part II: CYK Algorithm

1. The following grammar, Example 3.1.3 in L&P, generates syntactically correct arithmetic expressions containing + and *, and identifiers labeled by id:

E	=>	E+T \| T
T	=>	T * F \| F
F	=>	(E) \| id

A Chomsky normal form (CNF) version of this grammar is

E	=>	EN₁ \| TN₁ \| FN₁ \| idN₁ \| TN₂ \| FN₂ \| idN₂ \| (N₃
T	=>	TN₂ \| FN₂ \| idN₂
F	=>	(N₃
N₁	=>	+T \| +F \| +id
N₂	=>	F \| id
N₃	=>	E) \| T) \| F) \| id)

Using the CNF form above, or an equivalent one of your own devising, determine whether the strings

x =	(id + id)*id)
y =	(id) + (id*id)

are in the grammar by applying the CYK algorithm. Hand in a filled-in chart, like the one on the top of page 157 in L&P, for both strings.

Part III: More on CYK Algorithm

2. As presented in the book, the CYK algorithm is capable only of answering "yes, the input can be generated by the grammar" or "no, it cannot." How would you modify the algorithm so that, when the input string is indeed in the language generated by the grammar, then the algorithm produces a derivation (a parse tree) of the string in the grammar? A few sentences should suffice.