(Due at 4 pm on Friday, September 15))

NOTE: You should do this homework on your own, not with the help of others
in the class or outside the class.  You may ask for clarification of questions
from the TA or instructor.

PURPOSE: The purpose of this homework is to 
gain some experience reading and writing context free grammars.

1. Consider the context free grammar below in which nonterminals are 
written in upper case and terminals are written in lower case:

SENTENCE ::= PERSON APPRECIATES MUSIC | MUSIC APPRECIATES PERSON 
MUSIC ::= rocknroll | rap | jazz 
APPRECIATES ::= likes | loves | adores
PERSON ::= george | martha 

(a) Give a derivation and parse tree for the sentence:

	george loves rocknroll

(b) Is 
	rocknroll loves rocknroll 
    a legal sentence?  Why or why not?

(c) Show 5 legal sentences in this language.

(d) Show 5 illegal sentences in this language using the same set of
terminals.

2. A palindrome is a sequence of terminal symbols that
reads the same as its reverse.  For example, "mom" and madam i'm adam"
are both palindromes (up to the punctuation in the latter case).
Write a context free grammar for palindromes 
over the alphabet {a, b, c}.



Last Change: September 3, 2000 /
pollock@cis.udel.edu