CMPS 282 Final, Fall 2007

CMPS 282 — Software Engineering 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? 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? 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 (b) (5 points) string x contains exactly 2 different characters (c) (5 points) string x is a prefix of string y 3. (30 points) Write a Buchi automaton for the following properties. Assume the input alphabet is Σ = {a, b, c}, and that a, b, c are actions, i.e., each transition of the Buchi automaton is labelled with exactly one of a, b, or c. (a) (15 points) a cannot occur until b has occurred (b) (15 points) if a and b both occur, then subsequently c must occur 2 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. 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 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? 3