CSc 318   Final Examination   Monday  12 December 1994   7 PM
(Below ^ denotes a suprescript, e.g., 2^n denotes 2 raised to the nth power)

  1.  (10 pts)  Find a CFG which is not left-recursive and which is
    equivalent to the grammar       S--> Ax|By|c
                                    A-->Sy|By
                                    B-->a|b

  2.  (20 pts)  Given R and S, binary relations on the set A, prove that
       if R is a subset of S, then R^* is a subset of S^*.

  3.  (10 pts)  Find a lambda-free CFG, G', such that L(G')=L(G)-{lambda},
       where G is the CFG given by       S-->aBBaC|BC|bC
                                         B-->Ca|Cb|CC
                                         C-->abC|lambda

  4.  (10 pts)  If A={a,b,c,d} and B={0,1,2,....} prove that #B=#(A x B).

  5.  (20 pts)  Prove that for every regular expression, E, there is a CFG,
        G, such that L(G)=L(E) but that there is a CFG, G, for which there
        is no regular expression, E, such that L(G)=L(E).

  6.  (10 pts)  For the CFG below find an equivalent CFG which has all
        reachable and terminating symbols.    S-->CA|CB|BC|Ad
                                              A-->AD|BD|aBD|DE
                                              B-->caS|b|c
                                              C-->Ab|Bc
                                              D-->aA|Ab|bD
                                              E-->a

  7.  (20 pts)  Find a complete minimal DFA equivalent to the NFA given
    by M=({s,1,2,3,4},  {a,b,c},
          {(s,a,1), (s,c,2), (1,a,1), (1,b,2), (1,b,3), (2,a,3), (2,b,2),
           (3,b,4), (3,c,2), (4,a,s)},
           s,  {3,4})

  8.  (20 pts)  Given a complete DFA and states p and q, prove that if
     p and q are not i+1-distinguishable, then d(p,b) and d(q,b) are not
     i-distinguishable for each b in the input alphabet, where d is the
     transition function.

  9.  (10 pts)  Find a CFG in Greibach Normal Form which is equivalent
     to the CFG          S-->BaB|CbB
                         B-->CAB|a
                         C-->CaC|CbC
                         A-->a|b

 10.  (10 pts)  Find a CFG whose language is the same as the language of
     the NFA in question 7.

 11.  (10 pts)  Find a regular expression whose language is the same
     as the language of the NFA in question 7.

 12.  (10 pts)  Given R={(1,2), (2,4), (4,8), (8,9)} a binary relation
     on the set {0,1,2,3,4,5,6,7,8,9}, find R^*.

 13.  (20 pts)  Prove that for every CFG in 1-Standard Normal Form
     there exists an NFA with the same language.

 14.  (20 pts)  Given the three NFAs M=(Q,S,d,s,F), M'=(Q,S,d',s,F), and
    M"=(Q,S,d,s,F")   (where I had to use S instead of the usual sigma
     and d instead of the usual delta because of my wanting to use
     the ASCII set) prove
       (a)  F a subset of F" ==> L(M) is a subset of L(M")
       (b)  d a subset of d' ==> L(M) is a subset of L(M').