ProblemCOT 4420 -- Formal Languages and Automata Theory
Solutions

6.2#4.  Transform S -> aaAB, A -> bAB | l, B -> BAa | A | l into
  Chomsky Normal form.  (l = lambda) 

  Step 1.  Remove lambda productions: A -> l, B -> l.  For each
  production with A on the RHS, add new productions without A, without
  B, and without both A and B, and remove the lambda productions to get 
     S -> aaAB | aaB | aaA | aa, 
     A -> bAB | bB | bA | b, 
     B -> BAa | A | Ba | Aa | a

  Step 2.  Remove unit productions:  B -> A.  Form the dependency
  graph
	B --> A       S
  Add new productions B -> RHS of each non-unit production for A and
  remove the unit productions to get
     S -> aaAB | aaB | aaA | aa, 
     A -> bAB | bB | bA | b, 
     B -> BAa | Ba | Aa | a | bAB | bB | bA | b

  Step 3.  Construct the set of reducable productions and the
  dependency graph. 
  Dependency:  S --> A <--> B
  Reducable:  Initially {S, A, B} as all vocabulary symbols have
  productions with only terminals on the RHS.
  All nodes are reachable and all symbols are reducable.  There are no
  useless productions.

  Setp 4. Convert to Chomsky normal form (L -> MN, or L -> x).  If
  there are more than two terms on right, factor into two
  nonterminals and add productions yielding terminals
     S -> CE | CF | CG | CC, 
     A -> bAB | bB | bA | b, 
     B -> BH | BC | AC | a | DI | DB | DA | b
     C -> a, D -> b
     E -> CI, F -> aB, G -> aA, H -> Aa, I -> AB


6.2#8.  Show every CFG can be rewritten using only productions of the
  forms A -> aBC or A -> l where l = lambda and a in Sigma or a = lambda.
  Step 1. Rewrite in CNF so every production has form A -> aBC or A -> a
  Step 2.  Add a new production Z -> l
  Step 3.  For each production of the form A -> BC, replace it with
    A -> lBC.
  Step 4.  For each production of the form A -> a, replace it with
    A -> aZZ

6.2#11.  Convert S -> ABb | a, A -> aaB | B, B -> bAb to GNF.
Observer that the only problems are the productions S -> ABb and 
A -> B.
We can eliminate the unit production to get 
  S -> ABb | a, A -> aaB | bAb, B -> bAb.
Applying the substitution rule for A to ABb, we get
  S -> aaBBb | bAbBb | a, A -> aaB | bAb, B -> bAb.
which is in GNF.

6.2#12.  Convert S -> aSA, A -> bABC, B -> b, C -> aBC so that all
  productions have the form A -> xY where |Y| <= 2.
The only problem is the production A -> bABC.  By observation, we see
  that we can introduce the new production D -> BC = D -> bC and
  rewrite the grammar as
    S -> aSA, A -> bAD, B -> b, C -> aBC, D -> bC
  which has the required form

7.1#4a. Algorithm (corrected).  Push 2 a's for each a in put and pop one a for
    each b.  (Let l = lambda, x, y any other symbol)
    d(q0, a, z) = (q1, aaz)
    d(q0, l, z) = (q0, z)  //stay on lambda
    d(q0, x, y) = (q4, y)  //fail onanything else
    d(q1, a, a) = (q1, aaa)
    d(q1, b, a) = (q2, l)
    d(q1, l, y) = (q1, y)  //stay on lambda
    d(q1, x, y) = (q4, y)  //fail on anything else
    d(q2, b, a) = (q2, l)
    d(q2, l, z) = (q3, z)  //success when empty if no more input
    d(q2, l, x) = (q2, x)  //stay on lambda
    d(q2, x, y) = (q4, y)  //fail on anything else
    d(q3, l, z) = (q3, z)  //stay on success
    d(q3, x, y) = (q4, y)  //fail if there's more input
    d(q4, x, y) = (q4, y)  //stay on anything
  F = {q0, q3}

7.1#4b.  Push a's and b's until c.  On c, change to popping each
    matched a or b.  If stack is empty at end of input, success.
    Otherwise fail.

7.1#4c.  Push a's and b's.  Change to popping on first c.  For each c,
    pop an a or b from the stack.  Success if stack is empty at end of
    input.  Otherwise fail.

7.1#4h.  If the input is 'a' and
	     there is a z on top of the stack, push az
	     there is an a on top of the stack, push aa
	     there is a b on top of the stack, push c (= half b)
             there is a c on top of stack, push lambda
         If the input is 'b' and
	     there is a z on top of the stack, push bz
	     there is an a on top of the stack, push lambda
	        if there is a a on top of the stack, push lambda
                else if top of stack is z, push c
	     there is a b on top of the stack, push bbb
	     there is a c on top of the stack, push bc
	 Success if stack is empty at end of input, success
           else fail

7.1#10.  Since q2 is the only accepting state and since the only
  transition to q2 is on d(q0, a, z) we accept the string a.  If we
  get an a to start, we also go to q1, pushing an a.  The PDA stays in
  q1, pushing b for each b in the input until an a is encountered with
  b on the stack.  This causes a transition to the accepting state q2.
  Thus strings of the form abb*a are also accepted and L = L(a, abb*a).

7.2#3. When the input matches the terminal at the beginning or a RHS
  for the vocabulary symbol on the top of the stack, push the rest of
  the RHS of the production.  Match (pop) any terminal symbol.
  Consider the PDA with
       d(q0, l, z) = (q1, Sz)
       d(q1, a, S) = {(q1, Sbb), (q1, ab)}
       d(q1, a, a) = (q1, l)
       d(q1, b, b) = (q1, l)
       d(q1, l, z) = (q2, z)  //accept in q2.

7.2#4. d(q0, l, z) = (q1, Sz)
       d(q1, a, S) = {(q1, ABB), (q1, AA)}
       d(q1, a, A) = ({q1, BB), (q1, l)}
       d(q1, b, B) = (q1, bb)
       d(q1, l, B) = (q1, A)
       d(q1, a, a) = (q1, l)
       d(q1, b, b) = (q1, l)
       d(q1, l, z) = (q2, z)