Newsgroups: ucla.classes.cs.cs181
Subject: Collection of CS181 corrections for Spring 1995 as of 6/08/95
Distribution: ucla

----------------------------------------------------
ftp://ftp.cs.ucla.edu/pub/cs181/corrections.yy.mm.dd
----------------------------------------------------
Week10 Fri 6/ 9/95 2:20 am last modified
----------------------------------------------------
If you have any other corrections, please mail tsai@cs.  
Thanks to all of you who have been pointing out possible errors.

If you don't understand something, send me mail.
Either I can clear up the issue and/or we can correct/improve the
handouts.
------------------------------------------------------------------------------
PPANS8 #6a  Top line should read "S -> aT"
       #6c  The given PSG is totally wrong.

	    Use G = ({B,S,T,U,X},{a,b,c,d},P ,S):
		 1                          1

	    P :  S -> TU
	     1   T -> aTc | aX g.               n  n-1 2m 2m
		 U -> BBUdd | BBdd   Generate  a Xc   B  d  , n,m>=1

		cB -> Bc                        n 2m  n-1 2m
		XB -> bX             Producing a b  Xc   d

		 X -> c              Turn the X into a c.  We're done.

	    Another possibility is G = ({B,C,S,X,Y},{a,b,c,d},P ,S):
				    2                          2

	    P :  S -> aSC | aBC                n 2m-1  2m n 
	     2   B -> bbBdd | bXdd   Generate a b    Xd  C , n,m>=1

		dC -> Cd                       n 2m  n-1 2m
		XC -> bY             Make     a b  YC   d

		YC -> cY                       n 2m n 2m
		 Y -> c              Gives us a b  c d

	    Both of these grammars are context-sensitive grammars.

	    NOTICE how you should DESCRIBE how your grammars work.

HW7 Correction: 3c is NOT context-free.
   Full credit will be given to everyone.
   Extra credit for pumping lemma or closure proofs.

------------------------------------------------------------------------------
HW4 The proof for Homework 4, Problem 4 was confusing and incorrect.

      The algorithm misses size 0 palindromes.
      Size 1 palindromes are missed because the tests in step 4 
      are done in the wrong order.

Here is a new proof for Homework 4, Problem 4:

Note: We are marking state-pairs, not states.

1. FOR EACH f in F DO
     ENQUEUE (q0,f) and mark "OLD"
   ENDFOR

2. ANS = NO

3. WHILE ANS = NO and QUEUE is not empty DO
     DEQUEUE (r,s)
     IF r = s or s = d(r,a) for some a in SIGMA THEN 
       ANS = YES
     ELSE
       FOR each input a in SIGMA DO
	 r' = d(r,a) and s = d(s',a)
	 IF (r', s') is unmarked THEN
           ENQUEUE (r',s') and mark "OLD"
	 ENDIF
       ENDFOR
     ENDIF
   ENDWHILE
------------------------------------------------------------------------------
ANS5 (Sample Midterm - Winter 1990)
             *  *  *  * * *
     #3a  c(b ab ab ab ) b c  <- delete the last star on the right

     #4a  Left to Right derivation
	  S -> A1Y2 -> 0A1Y2 -> 00A1Y2
				^^^ <- add extra 0.

     #4b  Right parse tree -> Bottom symbol should be "0"

ANS4 #5   "5. Use Rabin-Scott to MAKE ...", not "makea"

HW4  #3   L7-10 should be renumbered L8-L11

     #2b  oddPAL should be defined with w in {a,b}*

		    +            +
     #2a  x  is in a , y  is in b , length of x  = length of y  for some k
	   i            i                      k              k
	
ANS3 #3b  FSL is closed under ... AND REVERSAL

HW2  p.4  In the SS statements, under not SS statements 
	  "IA<-1" should be deleted.

     #2b  ... you can show that THE FOLLOWING languages ...

HW1  #3b  ... in which AT LEAST one ...

PP1  #3a  ADD Note: asymmetric and anti-symmetric are different properties.

     #5   "Under what circumstances" should read 
	  "For which languages L is the following statement TRUE:"