Fall 2000, CSE 468: Assignment 6

Distributed: Published on the web on November 18.
Due: December 4 (in class).
Total maximum score: 100 points.
The purpose of this assignment is to to provide experience with parsing of context-free languages and with Turing Machines.

Please write your solutions as clearly and concisely as possible.

  1. (60 pts) Consider the langauge L generated by the following context-free grammar 
       S -> T$
   T -> TU | ab
   U -> aUbb | ab
    1. (10 pts) Define an equivalent LL(1) grammar by factoring and by eliminating left recursion.
    2. (20 pts) Define a deterministic PDA recognizing L, starting from the grammar defined in point 1, and applying the technique of the look-ahead.
    3. (30 pts) Define a Recursive Descent parser for L, based on the grammar defined in point 1.

  2. (40 pts) Give the diagram of a Turing machine that accepts the language L = {akbmckdm | k, m >= 0}