CS 154 Introduction to Automata and Complexity Theory Handout 3

Winter 1996  R. van Glabbeek  January 17, 1996

Problem Set 2 Date Due: January 22, 1996

Reading: Floyd and Beigel, Chapter 0-3.3 to be read by Wednesday January 24’th.

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. (10 points) 1.3-6 (page 86)

2. (10 points) Construct a 2-UCM program accepting {a^{n}b^{n}a^{n} | n ≥ 0}.

3. (10 points) Construct an SM program accepting {a^{n}b^{m}a^{m}b^{n} | m, n ≥ 0}. Hint: First try to construct an SM program accepting {a^{n}b^{m}a^{m}b^{n} | m > 0, n ≥ 0}, then derive a non-deterministic version.

4. (15 points) 2.10-4 (page 152). Hint: read exercise 0.6-29 before solving (c).

Extra Credit problem (optional) Solve 2.9-7 (page 151).