Answer Key for CSE-304 Mid-term Exam of Fall '98

1.
  a. b*(ab*ab*)*
  b. b*(ab*ab*ab*)*
  c. Start state: s0
     Final state: s1
     Transitions:
        From  To  Symbol
        s0    s0   b
        s0    s1   e (epsilon)
        s1    s2   a
        s2    s2   b
        s2    s3   a
        s3    s3   b
        s3    s1   e
  d. Start state: s0
     Final state: s1
     Transitions:
        From  To  Symbol
        s0    s0   b
        s0    s1   e (epsilon)
        s1    s2   a
        s2    s2   b
        s2    s3   a
        s3    s3   b
        s3    s4   a
        s4    s4   b
        s4    s1   e

2.
%%
\"[^\"]*\"  { yytext[yyleng-1] = 0 ; printf ("``%s''", yytext+1) ; }
.|\n   { printf ("%c", yytext[0]) ; }
%%
   
3.
  a&b. Number rules from 1 to 3. Let L -i-> R denote application of rule i
     that takes L to R. Then the two distinct  parse trees are the 
     result of the following rightmost derivations:

     I.  S -1-> aSbS -3-> aSb -1-> aaSbSb -2-> aaSbbSaSb -3-> aaSbSbab -3-> aaSbbab -3-> aabbab
    and another parse tree is:
     II. S -1-> aSbS -1-> aSbaSbS -3-> aSbaSb -3-> aSbab -1-> aaSbSbab -3-> aaSbbab -3-> aabbab

  c. First(S) = {a, b, e}
     Follow(S) = {$, a, b}

  d. G3 is not LL(1) since it is ambiguous.
  e. G3 is not SLR(1) since it is ambiguous.

4.
  a. State 10, TOK_exp, TOK_frac
  b.
     %left TOK_frac
     %nonassoc TOK_sqrt
     %right TOK_exp
  c. On TOK_exp, action shift is used. For others, reduce is used.

5.
  a. O(Sigma * Pi)
  b. O(n)
        It is a tree of n leaves. Apart from the nodes whose children
        are leaves, all other nodes are *binary*. So we have
        3n-1 nodes (n leaves, n immediate parents of leaves, n-1 internal
        binary nodes) in the parse tree