CSC 324, Summer 2001

Tutorial notes for week 3

****************************************************************


1.  Consider the grammar:

  <S> ::= <S> <S> | 0 | 1
  
  Show that this grammar is ambiguous:  
        Show two parse trees for the string 101.

  Write an unambiguous equivalent grammar. 

Hint: change the rules so that no more than one rule can succeed at any
given point in the derivation process. Sometimes more nonterminals need to
be introduced (not in this case).

  <S> ::=  0 <S>  |  1 <S> | 0 | 1



2. Consider the language described by the following regular expression
   over the alphabet {a,b,c,d,e,f,g,h}:

       (a|b*) cd (d|ef)+ gh*
       
   (Note that the '+' symbol in this expression should be read as a
    superscript, with its usual meaning for regular expressions.) 
    
   Now suppose that parts of this regular expression are labelled as
   follows:
   
       (a|b*)  cd  (d|ef)+  gh*
       ------  --  -------  ---
         A     B     C       D 
         
   For each of the following strings, if the string is in the
   language then show the parts of the string that correspond to
   the parts of the regular expression (labelled with capital   
   letters above). Do this by circling and labelling the appropriate
   parts of the string. If the string is not part of the language,   
   write 'NO'.

   a) abcdefgh
   
   b) cdefgh
   
   c) acdefghh
   
   d) bcdefghgh
   
   e) acdefdg
   
   f) cdg


   a) abcdefgh     -- NO                   b)    cd  ef  gh
                                               -  --  --  --
                                               A  B   C   D
 
   c) a  cd  ef  ghh                       d) bcdefghgh    -- NO
      -  --  --  ---
      A  B   C    D
 
   e) a  cd  efd  g                        f) cdg          -- NO
      -  --  ---  -
      A  B    C   D



3. Give regular expressions (RE) and CFG grammars (using BNF notation) 
for the following languages (or say it cannot be done)

a) All strings over the alphabet {0,1,2,3} sorted in decreasing order.
 
RE: 3* 2* 1* 0*

CFG: <S> ::= <threes> <twos> <ones> <zeros> | epsilon
     <threes> ::= 3 <threes> | epsilon
     <twos> ::= 2 <twos> | epsilon
     <ones> ::= 1 <ones> | epsilon
     <zeros> ::= 0 <zeros> | epsilon

Note that if you have the RE is easy to write the CFG following the
parts of the RE.

 
b) All strings over the alphabet {a,b} in which every b is both
      immediately preceded by and followed by at least one a.

RE: (a(ba)*)*

CFG:  <S> ::= a <X> <S> | epsilon
      <X> ::= b a <X> | epsilon

c) All strings of length 1 or more, made of characters from 1 to 5, such
that if you treat the string as an integer and add it to its reverse you
get a number made up completely of 6's. Examples: 12345, 3, 33, 333, 4152.

RE: cannot

CFG: <S> ::= 1 <S> 5 | 5 <S> 1 | 2 <S> 4 | 4 <S> 2 | 3 <S> 3 | 3 | epsilon

d) a^n b^m a^n b^m   n >= 0

cannot be expressed by RE
cannot be expressed by CFG


***********************************************************************

4. Brief intro/overview of the MIT Scheme environment.
On the cs or cdf machines, you say "scheme" to run Scheme.  Then you
can type function definitions or expressions to evaluate directly to
the interpreter, eg:
      
1 ]=> (+ 3 4 5)
;Value: 12

Note that ';' indicates a comment, and the expression after the ':' is
the value of the expression typed in.

To load a file with scheme code (myfile.scm, where .scm is the default
extension):

1 ]=> (load "myfile")

To exit scheme:  ^D   or
1 ]=> (exit)         

Try to following in Scheme (if you get an error explain why) :

1 ]=> (car (cons 'a '(b c))) 

1 ]=> (cdr (cons 'a '(b c)))

1 ]=> (cadr (cons 'a (cons 'b '(c))))

1 ]=> (cons '(a b c) (cons 'a (cons 'b (cons 'c '()))))
      
1 ]=> (null? (cddr '(a b c)))

1 ]=> (null? (cddr '(a b)))

1 ]=> (car '())

1 ]=> (cdr (car '(a b)))


We can draw the lists (the memory cells):
For example: 

'(a b)    -----      -----    
         | a |-|--> | b |\|
          -----      -----

'(a (b))    -----      -----    
           | a |-|--> |   |\|
            -----      -|---
                        v
                       -----
                      | b |\|
                       -----

****************************************************************

6) Define simple Scheme functions:

  (define (add x y)
    (+ x y)
  )

  (define (cube x)
    (* x x x) 
  )

 How to use them:
  (add 3 4)
  (cube 3)