Date: Wed, 08 Jan 1997 20:43:56 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 322 Assignment 4 Due Friday, January 26, 1996



next up previous
Next: About this document

CSE 322 Assignment 4 Due Friday, January 26, 1996

  1. Number 36 on page 69. Better yet construct the derivation tree for .
  2. Consider the grammar: .
    1. By example show that this grammar is ambiguous.
    2. Design an unambiguous grammar which generates the same language as this grammar. Explain why your grammar is unambiguous.
  3. Use the construction given in class for producing a regular grammar from a regular expression to construct a regular grammar which generates the language defined by the regular expression .
  4. Let L be the subset of where the a's and b's are matched as parentheses. The grammar G with productions . generates this language. Prove by induction on the length of a derivation that if and then x satisfies the two properties (i) every prefix of x has at least as many a's as b's and (ii) x has an equal number of a's as b's.

    Note that there is only one derivation of length 1, namely, . For the inductive step, if then there are two possibilities or . Your job is to carefully complete the induction proof using these ideas.





James Fix
Mon Jan 22 10:11:12 PST 1996