CMPS 282 Final, Spring 2008

CMPS 282: Software Engineering II Instructor: Paul C. Attie Department of Computer Science American University of Beirut Problem Set 2 Due: Tuesday April 15 The topic of this problem set is writing I/O Automata. 1 (20 points). (a) (10 points) Give an I/O automaton A such that: 1. A has a single start state. 2. A has two output actions x, y. 3. A has no states without an outgoing transition, i.e., from every state, either x or y or both can be executed. 4. In any finite execution of A, the number of occurrences of x and the number of occurrences of y differ by at most 1. (b) (10 points) Now modify the I/O automaton for (a) so that the number of occurrences of x and the number of occurrences of y differ by at most n, where n is some constant. 2 (15 points). Give an I/O automaton A such that: 1. A has a single start state 2. A has no states without an outgoing transition, i.e., from every state, at least one action can be executed 3. A has one input action x and one output action y 4. In any infinite execution of A, every occurrence of x is eventually followed by an occurrence of y (hint: recall that I/O automata are input-enabled, so in this case, the input x must be executable from every state of A). 3 (15 points). Give an I/O automaton A such that: 1. A has a single start state. 2. A has no states without an outgoing transition, i.e., from every state, at least one action can be executed. 3. A has one input action b and two output actions a, x. 4. In any execution α of A, if a is executed as some point, then x is not executed unless b is first executed. In other words, every “interval” in α from some occurrence of a until the first subsequent occurrence of b, does not contain any occurrence of x. 1