ProblemSet6 < CS301

CS301 Web>Syllabus>Homeworks>ProblemSet6 (2012-02-24, Main.sloan) (raw view)EditAttach
---++ Problem Set 6, CS 301, Spring 2012
   1 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.
      1 Fido likes the girl with the chocolate.
   1 For the simple ambiguous grammar S --&gt; (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
   1 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 (,),[,],{,}
      1 The set of all strings of the form <latex> a^* b^* </latex> that have exactly 3 b's for each a.
      1 The set of all strings of the form <latex> a^* b^* </latex> 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<em> must be even.</em>)
      1 The set of all palindromes over a,b.
      1 <latex> \{0^i 1^j 0^i : i,j \geq 0 \mbox{ and } j \mbox{ is even} \} </latex>
   1 Argue that if L1 is context free and L2 is context free, then so is L1 L2. (concatenation).
Grammar for subset of English:

S -&gt; NP VP

NP -&gt; &lt;CMPLX-NOUN&gt; | &lt;CMPLX-NOUN&gt; PP

VP -&gt; &lt;CMPLX-VERB&gt; | &lt;CMPLX-VERB&gt; PP

PP -&gt; &lt;PREP&gt; &lt;CMPLX-NOUN&gt;

&lt;CMPLX-NOUN&gt; -&gt; &lt;ARTICLE&gt; N | &lt;PROPER-NOUN&gt;

&lt;CMPLX-VERB&gt; -&gt; V | V NP

&lt;ARTICLE&gt; -&gt; a | the

N -&gt; boy | girl | flower | cat | dog | bear | chocolate | sushi | gun | camera

&lt;PROPER-NOUN&gt; -&gt; Fido | Tom | Dick | Harry

V -&gt; touches | likes | sees | smells | shot

&lt;PREP&gt; -&gt; with

-- Main.sloan - 2012-02-18
Topic revision: r2 - 2012-02-24 - 03:35:54 - Main.sloan
CS301
[edit this menu]
WISEST
Helping Women Faculty Advance
Funded by NSF