CS 154 Introduction to Automata and Complexity Theory Handout 17

Winter 1996  R. van Glabbeek  February 21, 1996

Problem Set 6 (II) Date Due: February 28, 1996

Reading: Floyd and Beigel, Chapter 0-7.9, except for 7.5, to be read by Wednesday February 28’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.

Homework 6 (I) correction In problem 3 you should do 6.1-2 on page 405 and NOT 6.4-2.

1. (10 points) Consider Figure 6.14 on page 433. It has 4 internal states ν_{1}, ν_{2}, ν_{3}, and ν_{4}. Construct a subprogram with only 3 internal states that achieves the same functionality.