CMPS 282 Final, Fall 2007

CMPS 282 — Software Engineering SAMPLE SOLUTIONS TO THE FINAL EXAM 2 hours January 22, 2008, 8:00 a.m., Bliss 203 Please draw a horizontal line across the page between the answers to each question You may refer to the following during the exam: • the course textbook • the course lecture notes • your homework solutions and my homework sample solutions You may not refer to any other materials, especially your project notes and writeups. Good luck! 1. (10 points) (a) (5 points) Consider the data model given in figure 1. Z Y W X Figure 1: Data model for question 1 (a) Given that all sets in the diagram are nonempty, what is the strongest relation between Y and W that can be concluded from the diagram? Solution. Y ∩ W ⊇ X ∧ X ̸= ∅. 1 (b) (5 points) Consider the data model given in figure 2. ! ? ! r1 r2 Z Y X ? Figure 2: Data model for question 1 (b) Consider the derived relation r3(x, z) ≜ (∃y : r1(x, y) ∧ r2(y, z)). To how many elements of Z can an element of X be related to, in general? Solution. 0 or 1 2. (15 points) You are given that x is a finite string of length n and y is a finite string of length m. Assume that x is indexed x1, . . . , xn, i.e., xi is the i’th character of x, and that y is similarly indexed y1, . . . , ym. State the following in first order logic: (a) (5 points) all characters in string x are the same Solution. (∀ i : 1 ≤ i < n : xi = xi+1) (b) (5 points) string x contains exactly 2 different characters Solution. (∃ i : 1 ≤ i < n : (∃ j : 1 ≤ j < n : xi ̸= xj ∧ (∀ k : 1 ≤ k < n : xk = xi ∨ xk = xj))) (c) (5 points) string x is a prefix of string y Solution. n ≤ m ∧ (∀ i : 1 ≤ i ≤ n : xi = yi) 2 3. (30 points) (Note: this question has been modified from Buchi automata to I/O automata). Write an I/O automaton for the following properties. Assume that b is an input action and a.c are output actions. (a) (15 points) a cannot occur until b has occurred Solution. State bseen: Boolean, initially false; Actions Input b Effect: bseen := true Output a Precondition: bseen Effect: none Tasks: {{a}} (b) (15 points) if a and b both occur, then subsequently c must occur State aseen: Boolean, initially false; bseen: Boolean, initially false; Actions Input b Effect: bseen := true Output a Precondition: true Effect: aseen := true Output c Precondition: aseen ∧ bseen Effect: aseen := false, bseen := false Tasks: {{c}} 4. (30 points) This question concerns your course project (a) (10 points) Describe informally the system that your project implemented (b) (10 points) Give (informally, in English) one of the domain properties that you assumed in your project (c) (10 points) Describe the evolution of your project in terms of the changes made, emphasizing the feedback from later phases of the life cycle to earlier phases. In other words, give the “history” of the project. 3 No solution provided since this is specific to the particular project. 5. (15 points) Given the following requirement R for an elevator system R: if user A is in the lift and user B is waiting at a floor, then user A reaches his/her destination floor before user B does 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. 2. The domain property defines the behavior of users A and B 3. The specification and domain property together imply the requirement, i.e., D, S ⊢ R. You must prove this by considering an example execution, as shown in class. You will receive half credit if S and D are correct but you do not provide a proof. You may use either English (must be precise) or Buchi automata Solution. Specification S: If a panel and a floor request are both pending, then the panel request is satisfied before the floor request is. Domain property D: A user waiting at a floor presses the appropriate up or down request button. A waiting user enters the elevator when it arrives. A user inside an elevator presses the appropriate panel button. 6. (BONUS QUESTION — 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. (a) (15 points) Given an input alphabet Σ = {a, a′, b, b′} of actions. Give the Buchi automaton that recognizes the language L of all infinite strings where: Every occurrence of action a is eventually followed by an an occurrence of action a′ and every occurrence of action b is eventually followed by an occurrence of action b′. You must give a single automaton, not a parallel composition of two or more automata Argue informally that your automaton is correct (b) (10 points) Suppose now Σ = {a1, a1′, . . . , an, an′}. Consider a Buchi automaton that recog- nizes the language for all i = 1, . . . , n, every occurrence of action ai is followed by an occurrence of action ai′. How many states (at least) does this automaton have? That is, what is the size of the smallest automaton that can recognize this language? 4