CSCI 410 Fall 2002
Midterm Solution

Problem 1:

Note: after the exam we decided to not count parts 1.2 and 1.5 towards
the total exam score, since we hadn't yet covered these topics in
class.  So the exam ended up being out of 48 points total.  (Spring
03: we just discussed the exact example that's in problem 1.5 in
lecture on 3/3).

1. b. Here's an informal argument for why an FSA is not powerful
   enough. Suppose the number of states in your FSA is n.  If there
   are more than n begins in the string, the FSA will run out of
   memory while reading begin's.  Since we can have an arbitrary
   number of begins, any FSA you choose won't have enough states.

2. c. If the list of actual parameters is followed by the list of
   formal parameters, FSA will run out of memory while still reading
   actual parameters. With PDA, when you push the formal parameters on
   to the stack and finally reach the first actual parameter, you can
   no longer compare the first actual parameter with what is in the
   bottom of the stack (first formal parameter). So, you need a turing
   machine for that.

3. a. Comparing each character to a finite set of illegal characters
   is enough.

4. a. Keep on advancing your input pointer and compare the current
   input to the string terminator. No need to keep track of what you
   have read already.

5. c. Similar to (2), you need to be able to search arbitrarily in
   both directions in the program. This you can't do with a FSM or a
   PDA.


Problem 2:

a. Follow
b. NFA, Regular expression
c. bottom-up


Problem 3:

a.

e-closure(1) = 125. This is our new starting state.


m(125, a) = 3, e-closure(3) = 3
m(125, b) = - (empty state)

When we are at state 125, at input a, we transition to 3, and at input
b, we transition to -

m(3, a) = -
m(3, b) = 4, e-closure(4) = 245

When we are at state 3, at input a, we transition to -, and at input
b, we transition to 245.

m(245, a) = 3
m(245, b) = -

When we are at state 245, at input a, we transition to 3, and at input
b, we transition to -.

The goal states are {125, 245} (all the states in which 5, the final
state from the NFA, appears).

The final table:

       a        b
125    3        -
  3    -       245
245    3        -

final states = {125, 245}

Note: 125 and 245 are state labels. You could have easily called them
X and Y. The labelling notation makes the translation easier.

It was not necessary to draw the diagram. Students who just drew the
diagram also got full credit.


b. (ab)*, or (a(ba)*b)*, or e|(ab)*|ab, or (ab(ab*))*, or e|(ab)+
There are many other possibilities, but the simplest one is (ab)*.


Problem 4:

a.

We start with the first item for the first production, and compute the
closure for that. This is how we get state 0:

Item set for state 0:

   E' -> .E
   E  -> .id
   E  -> .E=E


Then we compute closure of Goto set for each "state" for each terminal
and non-terminal and get the following unique states:

Item set for state 1:

   E' -> E.
   E  -> E.=E

Item set for state 2:

   E -> id.

Item set for state 3:

   E -> E=.E
   E -> .id
   E -> .E=E

Item set for state 4:

   E -> E=E.
   E -> E.=E


This is what the DFA looks like:

             Input
state    E     id    =
  0      1     2     -
  1      -     -     3
  2      -     -     -
  3      4     2     -
  4      -     -     3


It is ok to show the above table for the DFA or to draw a DFA.


b. There will be a shift reduce conflict in state 4.

Follow(E) = {$, =}, so we can reduce if next token is "=". However, it
is also possible to just shift and go to state 3.


action[4,=] has two possibilities:
         1. shift "=" and go to state 3
     or  2. reduce using E -> E=E

c.

It is enough to draw two different derivation tree for the same string
or to demonstrate two different left-most or right-most derivation
trees for the same string. Here is an example:

String: id = id = id


        -- id
E' -- E -- =      -- E -- id
        -- E -- E -- =
                  -- E -- id


                  -- E -- id
        -- E -- E -- =
E' -- E -- =      -- E -- id
        -- E -- id


d. shift

If we already have E=E on the stack and if the next input is =, if you
reduce, you would end up with E= in the stack from using the
input. Here we interpreted the input sequence as (E=E)=... (left
associative). Instead, if we shift, we will end up with E=E= in the
stack and later we will be able to interpret the input sequence as
E=(E= ..) (right associative).


Problem 5:

E -> E1 + T   { E.rev = T.rev + "+" + E1.rev; }
    | T       { E.rev = T.rev; }

T -> T1 * F   { T.rev = F.rev + "*" + T1.rev; }
    | F       { T.rev = F.rev; }

F -> id       { F.rev = id.lexval; }
    | (E)     { F.rev = "(" + E.rev + ")"; }


It is not only necessary to reverse the arguments for the binary
operators but also to concatenate the operators as "string"
value. Remeber, we are not trying to compute the value of the
expression. We want to output an expression that is reversed but with
all the operators intact.