CS 154 Introduction to Automata and Complexity Theory Handout 14

Winter 1996  R. van Glabbeek  February 14, 1996

Problem Set 6 Date Due: February 26, 1996

Reading: Floyd and Beigel, Chapter 0-7 to be read by Wednesday February 21’st.

Homework: Do the following exercises (FB refers to Floyd and Beigel The Language of Machines). Each problem must be submitted on a separate sheet. The homeworks must be solved without any collaboration.

1. (15 points) Convert the following context free grammar into GNF (Greibach Normal Form):

\begin{aligned}S & → & AA \\ S & → & a \\ A & → & SS \\ A & → & b \end{aligned}

2. (10 points) Do problem 6.2-5 (a) - (d) on page 413. Since the problem is very similar to the constructions done in the text we ask for a brief sketch of the constructions not less than 10 lines and not more than 30 lines.

3. (10 points) Do problem 6.4-2 (d) on page 405.

Extra credit (optional) Show that {xyyyz : x, y, z ∈ (0∪1)^{∗}, |y| ≥ 1} is not a DCFL (Deterministic context free language.