Fall 2000, CSE 468: Solution of Assignment 6
Exercise 1
 After eliminating left recursion, we get follows:
 S > T$
 T > abV
 V > UV  lambda
 U > aUbb  ab
 Then using factorization
 S > T$
 T > abV
 V > UV  lambda
 U > aW
 W > Ubb  b
 The following is a deterministic PDA for the language:
 lookahead:
 Alternative (3)/(4): choose (3) if next input symble is "a"; choose (4) if next input symble is "$"
 Alternative (6)/(7): choose (6) if next input symbol is "a"; choose (7) if next input symble is "b"


 The DPDA obtained with the technique of the lookahead

The recursivedescent parser is here.
Exercise 2