CMPS 282 Final, Spring 2007

CMPS 282 — Software Engineering FINAL EXAM 2 hours June 5, 2007, 8:00 a.m. Please draw a horizontal line across the page between the answers to each question 1. (20 points) The example below was discussed in class. The scope is given by 3 designations: comp(x, y) = x is a company employee during time interval y intl(x) = x is a time interval in the life of the company superior(x, y, z) = x is the manager of y in time interval z The description is for a “well-managed” company: 1. comp(x, y) ⇒ intl(y): if x is an employee during interval y, then y must be a time interval in the life of the company 2. superior(x, y, z) ⇒ comp(x, z) ∧ comp(y, z): if x is the superior of y during interval z then x and y must both be employees during interval y 3. superior(x1, y, z) ∧ superior(x2, y, z) ⇒ x1 = x2: an employee has at most one superior at any time Consider the following designation: bosses(x, z) = the set of superiors and superiors of superiors, etc. of employee x during time interval z, i.e., the “transitive closure” of the superior relation Note that bosses(x, z) is a function, not a relation (a) (10 points) Write a formal definition for bosses(x, z). Hint: use superior (b) (10 points) Using the definition in (a) state the following global constraint formally: no employee is their own boss 2. (30 points) Write a Buchi automaton for the following properties: (a) (15 points) if a occurs, then subsequently, either b occurs, or c and d both occur (in either order) (b) (15 points) if a occurs, then subsequently, b occurs and a does not occur again until the occurrence of b 1 3. (20 points) (a) (10 points) Consider the following module dependency diagram. Due to a mistake in the implementation of E, you have to change the specification of either X or of Y , but not both. Which specification should be changed? Explain your answer (no credit for writing just “X” or “Y ”). A B C D E X Y (b) (10 points) All else being equal, which of the following designs is preferable? Explain (no credit for writing just “design 1” or “design 2”). B D E F G C A A D C B E F G DESIGN 1 DESIGN 2 2 4. (15 points) Given the following requirement for an elevator system R: the door does not close if a person is standing in the doorway Give a specification S and a domain property D such that: 1. The specification is stated solely in terms of inputs and outputs to the system. You may assume appropriate sensors, but describe these carefully. 2. The domain property defines the correct behavior of the sensors. 3. The specification and domain property together imply the requirement, i.e., D ∧ S ⇒ R. 5. (15 points) A business rents jet skis by the minute. The owner would like statistics on usage to be computed at the end of each day, and implements a system for this purpose. When a jet ski is rented, an input of the form (“Start”, t) is given to the system, where “Start” is a constant character string, indicating the start of a rental session, and t is the time the session started. When a jet ski is returned, an input of the form (“End”, t) is given to the system, where “End” is a constant character string, indicating the end of a rental session, and t is the time the session ended. For each of the following statistics, state whether or not it can be computed from the inputs accumulated during the day. In each case, explain your answer, i.e., indicate how the statistic can be computed (from the inputs), or explain why it cannot be. (3 points for each answer). 1. the average session time for the day 2. the maximum session time for the day 3. the number of sessions completed (jet ski has been returned) during the day 4. the number of sessions that end before noon 5. the average length of all sessions that end before noon 3 6. (BONUS — 25 points) This question is substantially more difficult than the others. Do not attempt it unless you have finished all the other questions and checked your answers. Given a Buchi automaton A, the complement ¯A is a Buchi automaton where L( ¯A) = Σω − L(A). Recall that |A|, the size of A, is the number of states and transitions of A. If |A| = n, then there is an algorithm for constructing ¯A with | ¯A| = O(2(n2)). A deterministic Buchi Automaton is a 5-tuple (Q, Σ, δ, q0, F) where 1. Q is a set of states 2. Σ is a set of symbols, called an alphabet 3. δ : Q × Σ �→ Q is a transition function 4. q0 ∈ Q is a start state 5. F ⊆ Q is a set of accept states A deterministic Buchi automaton thus has at most one run on any input sequence. (a) (5 points) Let A1, A2, A3 be nondeterministic Buchi automata. What is the space complexity of determining whether L(A1) ∩ L(A2) ⊆ L(A3) is true, in terms of |A1|, |A2|, |A3|? (space complexity means the amount of memory needed) (b) (10 points) Given a deterministic Buchi automaton A = (Q, Σ, δ, q0, F), let A′ = (Q, Σ, δ, q0, Q− F), i.e., the set of accepting states has been complemented. Give an example A such that L( ¯A) ̸= L(A′), i.e., Σω − L(A) ̸= L(A′). (c) (10 points) Show that the powerset construction (from finite state automata) does not work for Buchi automata, i.e., cannot be used to determinize a nondeterministic Buchi automaton. Hint: give an example where the powerset construction fails. 4