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

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

Subject: <b>DFA equivalence question</b>
</a>


&gt; 
&gt; Q:  If a DFA accepts the language described by a regular expression, is 
&gt; it possible for the DFA to also accept strings that are not described 
&gt; by that regular expresssion?
&gt; 
&gt;     As a corollary... if you had to generate a DFA that accepts the 
&gt; language described by a regular expression, do you also have to ensure 
&gt; that the DFA rejects strings that are not in the language described by 
&gt; the regular expression.
&gt; 

Yes that's right, when you are determining whether a DFA accepts exactly the 
language described by a regular expression you need to ensure two things:
     1. that the DFA accepts the strings in the language described by the 
        regular expression
     2. that the DFA rejects the strings not in the language described by the
	regular expression.
Equivalently, you can show the following:
     1. every string accepted by the DFA is in the language described by 
        the regular expression
     2. every string in the language described by the regular expression
        is accepted by the DFA.
Note that these are just ways of showing that the two languages are equal.

It's real easy to find a DFA that satisfies only one of these two conditions:
the DFA that accepts every string of the alphabet trivially will accept any
string in a language described by a regular expression-- but it accepts
other strings as well.

This same reasoning explains why the behavioral lemma of problem 1 in
homework 7 is an &quot;if and only if&quot;-- to show that the construction of M 
from G is correct we need to say that it accepts _exactly_ L(G).

-j
<hr size=4><a name="825108836001">Date: Fri, 23 Feb 1996 12:53:51 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>hw9 corrections/clarification</b>
</a>


In problem 1, the text should read:

&quot;...Think of L as the set of arbitrary shuffles of strings from L(M1) and
                                   ^^^^^^^^
L(M_2).  For example, if aab is in L(M1) and bb is in L(M2) then
                     ^^
the strings aabbb, ababb, bbabb and many other strings are in L...&quot;


Also, you should notice (from the example) that in the definition of L,
the x_i's and y_i's are strings, not characters.  That's why the
language L contains shuffles of strings in L(M1) and L(M2) rather 
than just interleavings.

-j
<hr size=4><a name="825392357001">Date: Mon, 26 Feb 1996 19:39:12 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>question about behavioral lemmas..... </b>
</a>



---------- Forwarded message ----------
Date: Mon, 26 Feb 1996 19:38:33 -0800 (PST)
From: James Fix &lt;[e-mail]&gt;
To: Jason Murray &lt;[e-mail]&gt;
Subject: Re: question about behavioral lemmas.....


Regarding Friday's lecture:

&gt; Dr. Ladner was talking today about how we could not use q_not_prime and 
&gt; q_not in out behavioral lemma for the last homework.  I'm still not clear 
&gt; why this is.  My confusion comes from the example he did in class 
&gt; involving suffixes.  He was able to use q_not and q_not_prime in his 
&gt; behavioral lemma.  
&gt; 

One reason you might not want to refer to specific states in a behavioral 
lemma is due to the application of the induction hypothesis to prove the 
lemma.  For example, in the reversal problem, what you most likely wanted 
for a behavioral lemma was something that said that processing x in M' was
similar (in some way) to processing x^R in M.  Something like:

	for all p,q,x [p,x] |-*M' [q,lambda] iff [q,x^R] |-*M [p,lambda]

The inductive step for this would involve looking at this as
	[p,x] |-nM' [r,a] |-M' [q,lambda]
for some state r, ya =x, and invoking the induction hypothesis to say that
	[p,y^R] |-nM' [r,lambda].

If you instead fix p and q and state the B.L this way:
	
	for all x, p in F, [p,x] |-*M' [q0,lambda] iff [q0,x^r] |-M [p,lambda]

Then, you get in trouble because even though
	[p,x] |-*M' [r,a] |-M' [q0,lambda]
for some r in p, ya = x, you cannot conclude that
	[p,x] |-*M' [r,a]
from your induction hypothesis because your inductive hypothesis says nothing
about general r, just r in F.  It's too specific.

The reasons for how much you want to specify vs. generalize your B.L. are
somewhat analagous to the reasons for choosing strong vs. weak induction--
a general B.L. is more powerful and potentially more useful but may not 
be necessary:
	* a general B.L.  is more powerful because it says something
	  about more things.  You may need to prove the more general 
          version to get a clean inductive proof.  Often, a more general BL
	  is nicer because it says a lot about your construction of an M'.
	* a more specific B.L. is fine as long as:
		a) you can actually prove it without having to prove
                   the general B.L. in the process
		b) you can actually use it to prove the overall theorem
		   that you're trying to prove

In the suffix example in class, only the specific B.L. was necessary and
a more general B.L. was not obvious.

Hope this explanation wasn't too general,
-j




<hr size=4><a name="825393828001">Date: Mon, 26 Feb 1996 20:03:39 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: Jason Murray &lt;[e-mail]&gt;
cc: [e-mail]
Subject: <b>More HW9 corrections/clarifications</b>
</a>


In case you weren't sure, problem 3 should read:

&quot;...prove this by contradiction from first principles.&quot;

---------------------------------------------------------------------------
A question:
&gt; Since &quot;bbabb&quot; is in string L, is &quot;a&quot; or &quot;aaa&quot; also in string L?

oops.  No, bbabb, a, aaa are not necessarily in L, given only that aab 
and bb are in L.  See below for the correction.

Another:
&gt; I can't see how the third of the three examples bbabb can be constructed 
&gt; from aab and bb.
&gt; 
&gt; Am I missing something?
&gt; 

No, you're absoultely right.  The question should read:

&quot;...L(M_2).  For example, if aab is in L(M1) and bb is in L(M2) then
 the strings aabbb, ababb, bbaab and many other strings are in L...&quot;
                           ^^^^^
Sorry I did not catch this.  bbabb is not necessarily an element of L
since the number of a's and b's in it differs from the number of a's and 
b's in aab and bb combined.

--------------------------------------------------------------------------
The reason bbaab is in L is that, the xi's and yi's in the set expression 
can be lambdas.  So one way of getting the string bbaab to fit the 
set pattern is to let 

	n  := 2
	x1 := lambda
	x2 := aab
	y1 := bb
        y2 := lambda

In this way, we get (x1)(y1)(x2)(y2) = (lambda)(bb)(aab)(lambda) = bbaab,
and (x1)(x2) = aab and (y1)(y2)  = bb

Just to make this more clear, ababb is in L because if we let:
	
	n  := 3
	x1 := a
	x2 := a
	x3 := b
        y1 := b
	y2 := b
        y3 := lambda

we get (x1)(y1)(x2)(y2)(x3)(y3) = (a)(b)(a)(b)(b)(lambda) = ababb and
(x1)(x2)(x3) = aab and (y1)(y2)(y3) = bb.
        
--------------------------------------------------------------------------

Sorry for missing these before, I'll correct them on the web,
-j






<hr size=4><a name="826228482001">To: cse322@cs
Subject: <b>Homework 10, problem 1</b>
Date: Thu, 07 Mar 1996 11:54:33 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Instead of building a DPDA for the set of strings
with an equal number of a's as b's do it for the
following set.

L = {xc : x has an equal number of a's as b's}

L is in the alphabet {a,b,c}.

This small change will help you a lot.

Richard 
<hr size=4><a name="826320874001">To: cse322@cs
Subject: <b>Unclaimed homeworks</b>
Date: Fri, 08 Mar 1996 13:34:25 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


Sorry about the confusion getting homework 9 back
to you after class today.

I have 10 or so unclaimed homeworks from problem
sets 1 through 9.   I you would like to have
your homework back, please come by my office to pick
it up.  You can come by anytime, but you can
be sure I'll be in my office during my Monday-Tuesday
office hours from 11:00 to 12:00.

Richard
<hr size=4><a name="826331590001">Date: Fri, 8 Mar 1996 16:32:55 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>322 stuff</b>
</a>


Folks,

Just a reminder that my Study/Review Section will be
in Sieg 325 on Monday from 4:30-5:50.

Prof. Ladner will also be holding office hours 
on Monday and Tuesday from 11-12.

-j



<hr size=4><a name="826574627001">To: cse322@cs
Subject: <b>Star-Free Expression</b>
Date: Mon, 11 Mar 1996 12:03:36 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


You may have been wondering what the star-free
expression is for (ab)^*.  Let e be the
empty set, then it is the 

complement of the union of

(a e^-^-
(e^- b)^-
e^- a a e^-
e^- b b e^-.

To see this first recognize that e^- is simply
{a,b}^*.  Second, realize that
a string is not in (ab)^* if and only if

it does not begin with an a or
it does not end with a b or
it has two a's in a row or
it has two b's in a row.

Richard

<hr size=4><a name="826599356001">Date: Mon, 11 Mar 1996 18:55:39 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Office Hours on Tuesday</b>
</a>


I've decided to add office hours starting at 12pm in room 326.  Stop by 
if you have final questions.

-j
<hr size=4><a name="826654872001">Date: Tue, 12 Mar 1996 10:21:04 -0800 (PST)
From: <b>James Fix &lt;[e-mail]&gt;</b>
To: [e-mail]
Subject: <b>Homework 10</b>
</a>


Homework 10 is graded.  If you'd like to pick it up before
the exam, stop by Prof. Ladner's office sometime today.

Send me email if you have any questions, or see you at 12 in 326,
-j
<hr size=4><a name="826657881001">To: cse322@cs
Subject: <b>Re: determinism of parsing </b>
In-reply-to: Your message of &quot;Tue, 12 Mar 1996 10:59:48 PST.&quot;
             &lt;[e-mail]&gt; 
Date: Tue, 12 Mar 1996 11:11:11 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>



Question:

Didn't you mention in class a parsing method that was deterministic?

I thought bottom-up parsing was, but I'm incorrect, right?  Both top-down 
and bottom-up parsing are not deterministic, right?

If you did mention a parsing method that was deterministic (something 
about look ahead 1), should we review it?

Answer:

The parsing methods I described, top-down and bottom-up,
are nondeterministic.  However, if the grammar has the
right properties then one or both methods can be
made to be deterministic.  To make them deterministic
may require lookahead and the creation of many states.

I did mention in class that the bottom-up parsing method
is more generally used because it can handle more
context-free languages than the top-down method
and the grammars it handles tend to be nicer.

I mentioned several times that there are context-free
languages which are inherently nondeterministic.  Every
PDA accepting such a language is nondeterministic.

What I did not mention is that there is a parsing method,
that is never used in practice, which can parse any
context-free grammar.  This parsing method takes O(n^3)
time and is not practical.  it is a cool method though.

Richard
<hr size=4><a name="826825411001">To: cse322@cs
Subject: <b>Final Exams and Grades</b>
Date: Thu, 14 Mar 1996 09:43:25 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


As I mentioned at the final exam, I do not put out the
finals nor do I post grades.  

If you want your final back, and I hope you do, please
drop by my office anytime next quarter.  I would be 
very happy to see you.  

If you are anxious about your grade please send me e-mail
on or after Tuesday, March 19th, and I can reply with your
grade.

Have a good quarter break.  Maybe I will see you on the
slopes of Crystal Mountain, on March  22nd, 23rd or 24th.

Richard Ladner
<hr size=4><a name="827185471001">To: cse322@cs
cc: ladner@whalespout
Subject: <b>Grading Done</b>
Date: Mon, 18 Mar 1996 13:44:12 PST
From: <b>Richard Ladner &lt;[e-mail]&gt;</b>
</a>


I have completed the grading.  Final exams are available
from me in my office, 311 Sieg Hall.

Course stats:

Average grade: 3.4
Average Final Score: 71% 
Average Midterm Score: 81%
Average Homework Score 81% with 211 total points 

For the Final the highest score was 99% and the lowest 38%.
Final scores in the ranges:

90 - 100  6
80 - 89   6
70 - 79  15
60 - 69   7
50 - 59   6
40 - 49   3
30 - 39   1
-----------
total    44

I hope to see you when you pick up your exam.

Richard Ladner


</pre>
</body>
<hr>
<address>
<a href="mailto:[e-mail]">[e-mail]</a>
<br>
<a href="mailto:[e-mail]">[e-mail]</a>
<br>
(Last Update: 
   <!-- see man strftime for full formatting options-->
  01/03/96)
</address>

</html>