###
*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.

- (60 pts)
Consider the langauge L generated by the following context-free grammar
S -> T$
T -> TU | ab
U -> aUbb | ab

- (10 pts) Define an equivalent LL(1) grammar by factoring and by eliminating left recursion.
- (20 pts) Define a deterministic PDA recognizing L, starting from the grammar
defined in point 1, and applying the technique of the look-ahead.
- (30 pts) Define a Recursive Descent parser for L, based on the grammar defined in point 1.

- (40 pts)
Give the diagram of a Turing machine that accepts the language
L = {a
^{k}b^{m}c^{k}d^{m} | k, m >= 0}