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: About this document
CSE 322
Assignment 4
Due Friday, January 26, 1996
-
Number 36 on page 69. Better yet construct the derivation tree for
.
-
Consider the grammar:
.
-
By example show that this grammar is ambiguous.
-
Design an unambiguous grammar which generates the same language
as this grammar. Explain why your grammar
is unambiguous.
- 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
.
-
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