CS 154 Introduction to Automata and Complexity Theory Handout 4

Winter 1996  R. van Glabbeek  January 24, 1996

Problem Set 3 Date Due: January 31, 1996

Reading: Floyd and Beigel, Chapter 0-4 to be read by Wednesday January 31’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. (5 points) Refer to Example 3.1 starting on page 156 and its continuation after Theorem 3.2. Prove that ρπ_{2} = π′_{2}ρ.

2. (10 points) 3.3-9 (The one on page 190, not on page 194)

3. (15 points) Consider the alternative definition of acceptance given in Footnote 5 in Section 1.9: programs accept if every sequence of legal transitions leads to acceptance. Define a bisimulation as a relation of representation between the configurations of programs P and P′, that satisfies the conditions of a lockstep simulation of P by P′, and whose inverse satisfies the conditions of a lockstep simulation of P′ by P. Show that the existence of a bisimulation between two acceptors P and P′ guarantees that P and P′ are equivalent (i.e. that they accept the same language) under the alternative definition of acceptence. Your proof does not have to spelled out in great detail; the way I showed in class that the existence of a lockstep simulation guarantees that P and P′ are equivalent under the standard definition is formal enough.

4. (15 points) Design a lockstep simulation of a signed counter machine by an unsigned counter (and control with realm {+, −}). Your solution should preserve determinism. In your answer you should:

+ Give the relation of representation. + Present the simulation as in table 3.3 page 186.

- You don’t have to draw commuting diagrams.