http:^^www.cs.washington.edu^education^courses^322^96w^cse322-bboard.shtml

来自「This data set contains WWW-pages collect」· SHTML 代码 · 共 1,278 行 · 第 1/3 页

This is the kind of question you should ask as
early as possible. Part a) gives at least one
solution to the equation and part b) is not trivial because there
may be many different solutions to the equation.
<hr size=4><a name="821494798001">To: cse322@cs
Subject: <b>Student Solutions Book</b>
Date: Fri, 12 Jan 1996 16:59:50 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


There is a Student's Solutions Manual to Sudkamp's book.
I have ordered some for the bookstore and they should
arrive in a couple of weeks.  In the meantime, I will
hand out some copies for chapters 2 and 3 in class
on Wednesday.  I cannot copy the whole book without
violating copyright laws.

Richard 
<hr size=4><a name="821561128001">To: cse322@cs
Subject: <b>Tuesday office hours</b>
Date: Sat, 13 Jan 1996 11:25:22 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Students in CSE 322.

Something important has come up and I cannot make my Tuesday
11 - 12 office hour on January 16th.

I will hold a special office hour from 3 - 4 on Tuesday,
Jan 16th instead.

I hope that this is not inconvenient for you.

Richard
<hr size=4><a name="822343275001">To: cse322@cs
Subject: <b>Error in Handout</b>
Date: Mon, 22 Jan 1996 12:41:08 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


A student pointed out a slight error in the handout 
&quot;Construction of Regular Grammars from Regular Expressions.&quot;
In case 2 we should remove the A -&gt; lambda productions from
G_alpha before and not after adding the new productions.
Otherwise a problem would arise if bouth S_alpha -&gt; lambda
and S_beta -&gt; lambda were both productions in the original
grammars.  

I will show you the correction in class on Wednesday, or you
can get a preview sometime today when Jim puts the handout
on the Web.

This is a subtle error and it is good to see a student find it.

Richard
<hr size=4><a name="822344834001">Date: Mon, 22 Jan 1996 13:07:03 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: Andrew Petty &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>Re: hw4</b>
</a>



On Fri, 19 Jan 1996, Andrew Petty wrote:

&gt;  
&gt; Problem 1: 
&gt; 
&gt; (i) We turn-in the derivation tree only, or also the
&gt;     line by line derivation?

You can either turn in the line-by-line derivation *or* the derivation 
tree.  Your choice.  (I'm partial to the tree, since it saves my hands
from too much writing)

&gt; 
&gt; (ii) It takes several rules to derive,
&gt;      &lt;expression&gt; =*=&gt; &lt;letter&gt; =&gt; x 
&gt;      Since we have to do this for x, y, z can we just put a * next to the
&gt;      child arrow that points to the end result (once it has been 
&gt;      previously derived) ? Shouldn't there also be some note by the star
&gt;       reading something like 'by steps a thru n' (this would require
&gt;      labeling the relavent child arrows on the tree)? What do you suggest.
&gt; 
Any well-documented shorthand is fine, as long as you have gone through
some version of the derivation of a single-letter variable at least once, 
and your shorthand is very clear.

&gt; (iii) In example 3.6.2 p67 there is a sub-derivation;
&gt;      &lt;identifier&gt; =&gt; &lt;letter&gt;&lt;identifier tail&gt; =&gt; x&lt;identifier tail&gt; =&gt; x
&gt;      In the Pascal lang. spec, I dont see anything like
&gt;      &lt;identifier tail&gt;.  Did I miss it? Instead I see
&gt;      &lt;identifier&gt; =&gt; &lt;letter&gt;{&lt;letter or digit&gt;}.  If I want only one 
&gt;      x do I write &lt;identifier&gt; =&gt; &lt;letter&gt;{&lt;letter or digit&gt;} =&gt; 
&gt;      x{&lt;letter&gt;} =&gt; x (since I take {u} to mean zero or more reps of 
&gt;      u)?  Or can I just write 
&gt;           &lt;identifier&gt; =&gt; &lt;letter&gt; =&gt; x ?
&gt;      What is the proper way to terminate an identifier?
&gt; 
&gt;      Maybe your response will also answer this:
&gt; 
&gt;      If I want to derive 12 from &lt;unsigned integer&gt;
&gt;      do I write 
&gt;      &lt;unsigned integer&gt; =&gt; &lt;digit&gt;{&lt;digit&gt;} =&gt; 1 {&lt;digit&gt;} =&gt; 12
&gt; 
&gt; Sorry for such a long message....
Good observation.  Grammars in BNF are slightly different than context free
grammars as we have defined them since they include the bracket notation
{&lt;stuff&gt;}, which means concatenate &lt;stuff&gt; 0 or more times.   The intro
to appendix II discusses this issue.  One thing: you should convince yourself
that BNF grammars can be easily converted to our CFGs.  For example,
in the homework, replace the following BNF productions with their CFG 
equivalents:

BNF:
&lt;unsigned integer&gt; -&gt; &lt;digit&gt; { &lt;digit&gt; }
CFG:
&lt;unsigned integer&gt; -&gt; &lt;digit&gt; | &lt;digit&gt; &lt;digits&gt;
&lt;digits&gt; -&gt; &lt;digit&gt; &lt;digits&gt; | \lambda

BNF:
&lt;identifier&gt; -&gt; &lt;letter&gt; { &lt;letter or digit&gt; }
CFG:
&lt;identifier&gt; -&gt; &lt;letter&gt; &lt;identifier tail&gt;
&lt;identifier tail&gt; -&gt; &lt;letter or digit&gt; &lt;identifier tail&gt; | \lambda

where \lambda is the empty string.  You can use these CFG productions
instead of the BNF ones to answer problem 1.

Hope this helps.

-j

<hr size=4><a name="822348549001">Date: Mon, 22 Jan 1996 14:09:02 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Study Section</b>
</a>



Starting tomorrow, I'll be holding an informal study section every week.
My plan is to do any of the following:

	a) go over some of the questions from previous homeworks
	b) do some example questions from the book that are related
	   to the upcoming homework or to material previously covered 
	   in class
	c) answer random questions
	d) cover any general techniques (proofs by induction, set notation)
	e) answer random questions

the time and place:

	Tues. 2:30-3:30p
	Sieg 231

If you can't make it at this time because of another class, please
send me mail so I can keep track of you.

-j

<hr size=4><a name="822682148001">To: cse322@cs
Subject: <b>Midterm Exam</b>
Date: Fri, 26 Jan 1996 10:48:50 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


For the midterm exam on Wednesday, Jan 31, bring an 11 x 8 1/2 inch
blue book with 24 pages.

You may use the first 6 pages of the blue book for notes to 
help you during the exam.  Your notes must be handwritten
in the book.

Otherwise the exam is closed book.

The exam will cover the following chapters and sections
in the book.

Chapter 1, especially sections 1.3 and 1.6.
Chapter 2, all sections
Chapter 3, all sections
Chapter 4, sections 4.1

You should also know how to convert a regular expression to
a regular grammar and how to execute the top-down parsing
method.

Good luck on the exam.

Richard L.
<hr size=4><a name="822688441001">To: cse322@cs
Subject: <b>Correction in Assignment 5</b>
Date: Fri, 26 Jan 1996 12:33:12 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


The production T -&gt; F*E should by T -&gt; F*T instead.

I will correct this on the Web version of the
problem set.

Sorry for any inconvenience.

Richard
<hr size=4><a name="822691719001">Date: Fri, 26 Jan 1996 13:28:27 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Correction on HW#3 solns</b>
</a>


While we're admitting our mistakes:

In the section rambling about set notation, the third expression 

     *          &lt;=== times
{a,b} {c}

should read

     +          &lt;== plus
{a,b} {c}

Since there are strictly more than 0 a's or b's.  (i &gt; 0)


My apologies,
-j

	
<hr size=4><a name="822936787001">To: David Shaw &lt;[e-mail]&gt;
cc: cse322@cs
Subject: <b>Re: Midterm Exam </b>
In-reply-to: Your message of &quot;Sat, 27 Jan 1996 21:02:47 PST.&quot;
             &lt;[e-mail]&gt; 
Date: Mon, 29 Jan 1996 09:32:35 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Question:

I haven't bought the blue book yet, but do you mean each side of the page 
count as 1 page?

Answer:

Yes, six pages if your were to number the pages
1 to 24 in the blue book.
I don't believe it would benefit you to write
more notes, as writing 6 pages means you have
to think about discriminating the important
stuff from the less important stuff.

Richard
<hr size=4><a name="822965574001">Date: Mon, 29 Jan 1996 17:32:46 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Solutions to assignment 4...</b>
</a>


...are sitting in the &quot;handouts&quot; bins outside Prof. Ladner's office.  Get 
them while they're hot.  My apologies for the delay-- these problems were a 
bit involved as you all know.

They will also be put on-line, as will the corrections to solutions #1 
&amp; 3 that were discussed in class today.

Please let me know if you find any problems or have any questions--

-j
<hr size=4><a name="823293355001">To: cse322@cs
Subject: <b>Resumes</b>
Date: Fri, 02 Feb 1996 12:35:46 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


I mentioned the student resume list in class to day, but I forgot
to mention it is run by the Student Chapter of the Washington
Software Association (WSA).  There is a small fee for joining WSA
before your resume can be posted.  I think it might be worth
the small fee to post your resume.

Richard Ladner
<hr size=4><a name="823303061001">To: cse322@cs
Subject: <b>Bottom-down?</b>
Date: Fri, 02 Feb 1996 15:17:22 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Question:

While you've got me in pine... The homework assignment asks for a 
bottom-down parse. Do you really want a bottom-up parse?

Answer:

If you should do bottom-down you will no doubt drown, so better
try bottom-up as described in class today.
<hr size=4><a name="823628947001">To: [e-mail]
cc: cse322@cs
Subject: <b>Why context-free</b>
Date: Tue, 06 Feb 1996 09:48:46 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Question:
 
Can you explain what the &quot;context-free&quot; part of &quot;context-free 
language&quot; means?  I can't figure out what context it is refering to.

Answer:

In the early days of grammar research there was interest
in other kinds of grammars.  For example, you could
imagine a production of the form AB -&gt; CDE.  That is,
if you see the string AB in a sentential form, then you
can make a derivation step that replaces the AB with CDE.
Context-free grammar do not allow these kinds of productions.
The &quot;context&quot; refers to there being more than one symbol to
match when doing a derivation step.

<hr size=4><a name="823648432001">To: cse322@cs
Subject: <b>Textbook Error</b>
Date: Tue, 06 Feb 1996 15:13:43 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


A student pointed out the following error in the
text.  Exercise 29 on page 68.  The question refers to a language that is the set of all 
strings with a positive, even number of a's over {a,b}, and describes it 
with the regular expression (b^*ab^*ab^*)^*. The question also refers to 
the grammar:
		S -&gt; AA
		A -&gt; AAA | bA | Ab | a.

Since the empty string is in the language defined by the
expression and not in the language generated by the grammar,
then it is impossible to prove they are equivalent.
To make them equivalent just add the production S -&gt; lambda
or change the expression to (b^*ab^*ab^*)^+.


<hr size=4><a name="823798882001">To: cse322@cs
Subject: <b>Office hours today</b>
Date: Thu, 08 Feb 1996 09:01:14 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


I may be 15 minutes late for my office hour today.

Richard Ladner
<hr size=4><a name="823822918001">To: cse322@cs
Subject: <b>Lazowska &quot;almost live&quot;</b>
Date: Thu, 08 Feb 1996 15:41:47 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


I highly recommend you see this lecture!

Richard Ladner

---------------------------

University of Washington Presents the 20th Annual Faculty Lecture

&quot;A Half Century of Exponential Progress in Information Technology:
Who, What, When, Why and How&quot;

Professor Edward Lazowska
Chair, Department of Computer Science and Engineering

Watch UWTV, cable channel 27, on the following dates:
March 3, 8pm
March 10, 8pm
March 17, 9pm
March 24, 9pm

This program was recorded February 6 on the University of Washington campus.
<hr size=4><a name="823824925001">Date: Thu, 8 Feb 1996 16:15:20 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>reminder about DFAs</b>
</a>


Just a reminder about the definition of DFAs:

When you are constructing your DFAs for HW 6, remember that
delta is a _function_ Q x Sigma -&gt; Q and must be fully defined.
This means that for every state in Q, there should be _exactly one_
transition from that state for every character.  

On page 142, the book gives an example of a DFA where the
transition function is not complete (6.3.7) but then converts it
to a fully specified DFA (6.3.8) by adding an &quot;error&quot; state.  You
may need to do the same for some of the DFAs on the homework.

Once again, the general rule is:

	For a DFA, every state must have one outgoing arrow for 
        every character in the alphabet.

-j

<hr size=4><a name="824413747001">Date: Thu, 15 Feb 1996 11:47:49 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: sliqyboy &lt;[e-mail]&gt;
cc: [e-mail], [e-mail]