ProblemSet6 < CS301

Problem Set 6, CS 301, Spring 2012

Below is a modest extension of the context-free grammar for English from Sipser, p. 101, using the variable S for Sentence, NP for Noun Phrase, VP for Verb Phrase, PP for Prepoositional Phrase, N for Noun, and V for Verb. For each of the following two sentences, please give two different parse trees, and circle the one that is almost certainly the intended meaning of the sentence.
1. The boy shot Fido with the gun.
2. Fido likes the girl with the chocolate.
For the simple ambiguous grammar S --> (S) | S + S | S * S | id over the terminals (, ), *, +, id that we discussed in lecture, show at least three different parse trees for the string id+id*id*id
Construct PDAs for the following languages in JFLAP. Be aware that JFLAP uses the convention that the PDA's initial state has the special bottom-of-stack symbol Z on the stack at the start of time. You can take advantage of that if you want.
1. The language of balanced delimiters over the six characters (,),[,],{,}
2. The set of all strings of the form a^* b^* that have exactly 3 b's for each a.
3. The set of all strings of the form a^* b^* where the number of b's is 1 more than 1.5 times the number of a's. (Notice that this means the number of a's must be even.)
4. The set of all palindromes over a,b.
5. \{0^i 1^j 0^i : i,j \geq 0 \mbox{ and } j \mbox{ is even} \}
Argue that if L1 is context free and L2 is context free, then so is L1 L2. (concatenation).