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.
- The boy shot Fido with the gun.
- 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.
- The language of balanced delimiters over the six characters (,),[,],{,}
- The set of all strings of the form a^* b^* that have exactly 3 b's for each a.
- 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.)
- The set of all palindromes over a,b.
- \{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).
Grammar for subset of English:
S -> NP VP
NP -> <CMPLX-NOUN> | <CMPLX-NOUN> PP
VP -> <CMPLX-VERB> | <CMPLX-VERB> PP
PP -> <PREP> <CMPLX-NOUN>
<CMPLX-NOUN> -> <ARTICLE> N | <PROPER-NOUN>
<CMPLX-VERB> -> V | V NP
<ARTICLE> -> a | the
N -> boy | girl | flower | cat | dog | bear | chocolate | sushi | gun | camera
<PROPER-NOUN> -> Fido | Tom | Dick | Harry
V -> touches | likes | sees | smells | shot
<PREP> -> with
-- Main.sloan - 2012-02-18
Topic revision: r2 - 2012-02-24 - 03:35:54 - Main.sloan