Test 1       

  1. Give the regular expression for non-vanity Indiana license plates.

        ((1-8)(0-9) | 9 (0-2) | (1-9))
        (A-Z)
        ((1-9) | (1-9)(0-9) | (1-9)(0-9)(0-9) | (1-9)(0-9)(0-9)(0-9))
     
  2. Give the NFA for the regular expression: (a|b)*abb   

  3. Convert the NFA of Question 2 to a DFA. 

    ε-closure of single state s is the set of states reachable by a series of 0 or more ε-transitions, written as s. The ε-closure of state s always contains state s itself.

    Example: NFA for regular expression for a* has  1= {1,2,4}, 2= {2}, 3= {2,3,4}, 4= {4}

    ε-closure - S, of a set of states is the union of the ε-closures of each individual state s: S=Ès

    Example: {1,3} = 1È3 = {1,2,4} È {2,3,4} = {1,2,3,4} 

    DFA M construction from NFA M

    1. Compute ε-closure from start state of NFA M, becomes the start state of DFA M.

    2. For this set and each subsequent set compute transitions on characters a by:

      1. Given set S of states and character a, compute S'a = { t | for some s in S there is a transition from s to t on a}

      2. Compute S'a, ε-closure of S'a. Defines new state in DFA subset construction with a new transition on a of S ® S'a.

      3. Continue until no new states or transitions are created.

    3. Mark as final in M those states marked as final in M.

    DFA[A]=0= {0,1,2,4,7}
    DFA[B]=Aa={0,1,2,4,7}a ={3,8}={1,2,3,4,6,7,8} DFA trans[A,a]=B
    DFA[C]=Ab={0,1,2,4,7}b =5={1,2,4,5,6,7} DFA trans[A,b]=C
                      {1,2,3,4,6,7,8}a ={3,8}={1,2,3,4,6,7,8} DFA trans[B,a]=B
    DFA[D]=Bb={1,2,3,4,6,7,8}b ={5,9}={1,2,4,5,6,7,9} DFA trans[B,b]=D
                Ca={1,2,4,5,6,7}a ={2,7}={1,2,3,4,6,7,8} DFA trans[C,a]=B
                Cb={1,2,4,5,6,7}b =5={1,2,4,5,6,7} DFA trans[C,b]=C
    DFA[E]=Db={1,2,3,4,6,7,9}b ={5,9}={1,2,4,5,6,7,10} DFA trans[D,b]=E
                Da={1,2,3,4,6,7,9}a ={3,8}={1,2,3,4,6,7,8} DFA trans[D,a]=B
                Ea={1,2,4,5,6,7,10}a ={3,8}={1,2,4,5,6,7,8} DFA trans[E,a]=B
                Eb={1,2,4,5,6,7,10}b =5={1,2,4,5,6,7} DFA trans[E,b]=C

    (a|b)*abb

  4. Translate Question 2 into a context-free grammar.

    e = (a|b)*abb

    auxAB = a
    auxAB = b

    e = auxAB e
    e = abb
     
  5. Using the following grammar, give the parse tree for: a:=3; b:=a+2; print(b);

                                             S     
                                   /          |    \
                                 S            ;      S            
                          /       |  \               /      |  |  \
                       S         ;    S           print  (  L   )  
                  /    |   \       /    |     \                |         
                id    :=  E     id   :=    E               E
                /           |      |         / | \             |
               a          num   b       E + E           id
                                           /         \
                                          id        num
                            
  6. Give FIRST(E) for Grammar 3.1
    Given a non-terminal X, the set FIRST(X) consists of terminals and possibly є is defined as:
    1. if X is a terminal or є then FIRST(X)=X.
    2. if X is a non-terminal the for each production X ® X1X2...Xn , then FIRST(X) contains FIRST(Xi)-{є}.
    3. if FIRST(X1), FIRST(X2)...FIRST(Xi) contain є where i<n then FIRST(X) contains FIRST(Xi+1)-{є}
    4. if all FIRST(X1), FIRST(X2)...FIRST(Xn) contain є then FIRST(X) contains є

    FIRST(E)={ id num ( }
     

  7. Give FOLLOW(E) for Grammar 3.1
    Given a non-terminal A, the set FOLLOW(A) consists of terminals and possibly $ is defined as:
    1. if A is a start symbol then $ is in Follow(A).
    2. if production B ® a A g , then First(g)-{є} is in Follow(A)
    3. if production B ® a A g , such that є is in First(g), then Follow(A) contains Follow(B); since whatever follows B can follow A when g=є
    4. if production B ® a A, then Follow(A) contains Follow(B); since whatever follows B can follow A

    FOLLOW(S)={ ; , $ }
    FOLLOW(L)={ , ) }
    FOLLOW(E)={ + } È FOLLOW(S) È FOLLOW(L) = { + , ) ;  $ }
     

  8. Given the FIRST and FOLLOW sets, give the predictive parsing table, that is for top-down parsing. Aho p.188
     
    E ® TE'                       
    E' ® +TE' | є       
    T ® FT'                      
    T' ® *FT' | є              
    F ® (E) | id                           		FIRST(E)=FIRST(T)=FIRST(F)={(,id}
    FIRST(E')={+, є}
    FIRST(T')={*,є)    		 FOLLOW(E)=FOLLOW(E')={$,)}
    FOLLOW(Q)={$,)}
    FOLLOW(T)=FOLLOW(T')={+,),$}
    FOLLOW(F)={+,*,),$}

  9. Given the following bottom-up parse table, parse: i + i * i
     
    Stack Input Action
    0 i s5
    0i5 + r8
    0F3 + r6
    0T2 + r3
    0E1 + s6
    0E1+6 i s5
    0E1+6i5 * r8
    0E1+6F3 * r6
    0E1+6T11 * s8
    0E1+6T11*8 i s5
    0E1+6T11*8i5 $ r8
    0E1+6T11*8F13 $ r4
    0E1+6T11 $ r1
    0E1 $  
  10.  Construct the SLR(1) parse table for the following grammar, FOLLOW sets and DFA. Grune p.164
     
    1. Z ® E$
    2. E ® T
    3. E ® E + T
    4. T ® i
    5. T ® (E) 
    		FOLLOW(Z)={$}
    FOLLOW(E)={+,),$}
    FOLLOW(T)={+,),$}