(Last modified Fri May 30 15:41 2008)

1. Grammars 18 points total

   8 pts • Construct a CFG that generates the infinite set of sentences including the sentences below and all reasonable extensions of them that begin with S, end with U or D, and describe something an elevator might do.  The alphabet is: 

   • S: the elevator car stops at a floor. 
   • n: the doors open. 
   • o: the doors become completely open. 
   • b: the doors close. 
   • c: the doors become completely closed. 
   • U: the elevator car starts moving up. 
   • D: the elevator car starts moving down. 

   The symbols can appear more than once, but no symbol appears twice in a row, ever (it wouldn't make sense). 

   The sentences: 

   • S n o b c D
   • S n o b c U
   • S n o b c D S n o b c U
   • S n o b c U S n o b c D S n o b c U

   8 pts • Describe in words what each rule of your grammar does.  A rule without a clear explanation is too hard to grade and will receive no credit.  2 pts • Make the first rule's LHS be the grammar's start symbol. 

   Hint:  it can be done with four nonterminals and six rules. 

2. Statecharts 40 points total

   16 pts • Construct a statechart that describes an elevator car's movement up and down, and its doors opening and closing, and has the required states, input events, and actions listed below.  8 pts • Write a textual scenario that describes how the elevator works, in terms of your statechart.  16 pts • Verify that your statechart has the five properties listed below, and explain (for each property) why your statechart has that property. 

   Don't worry about the details of what makes the elevator car move up or down — the scheduling algorithm that reads the call button presses and controls which way the elevator moves next.  That's pretty complicated to express in a statechart.  Instead, just assume your statechart has inputs available to tell it to go up, down, or stop (see list of inputs below). 

   Your statechart must have states named

   • CarMovingUp that the elevator is in while the car is moving up; 
   • CarMovingDown that the elevator is in while the car is moving down;  and
   • CarStoppedAtFloor that the elevator is in while the car is stopped at a floor.  This should be a composite state because the doors change state while the car is stopped at a floor. 

   Your elevator must also have states named

   • DoorsClosed that the elevator is in while its doors are completely closed; 
   • DoorsOpening that the elevator is in while its doors are going from completely closed to completely open; 
   • DoorsOpened that the elevator is in while its doors are completely open; 
   • DoorsClosing that the elevator is in while its doors are closing;  and
   • any other states you need to make your elevator specification describe the elevator properly (you will probably need several).  Remember to define (in words) what each of these other states means.  Keep in mind that
     • you need two different states rather than a single state if sometimes one action needs to occur during the state, and other times a different action needs to occur during the state. 
     • you may need two different states rather than a single state if the choice of which state is next depends on what happened in the past (because each state represents all the paths that can lead to it).  For a FSM you will need two different states in that case, but Statecharts can have guard conditions on transition events that can sometimes handle this for you. 
   Probably if you have more than 15 or so states, and certainly if you have 20 states or more, you are making it too complicated. 

   Your elevator uses all these input events (and no others):

   • goUp.  The elevator receives this input whenever it is time for the elevator to go up. 
   • goDown.  The elevator receives this input whenever it is time for the elevator to go down. 
   • stopAtFloor.  The elevator receives this input whenever it is time for the elevator to stop at a floor. 
   • obstructed.  The elevator receives this input whenever the doorway becomes obstructed so that the door can't close.  This input comes from a sensor of some sort. 
   • clear.  The elevator receives this input whenever the doorway becomes clear so that the door can close safely.  This input comes from the same sensor. 
   • extendedOpen:  The elevator receives this input whenever someone presses the extended door open button. 
   • opened:  The elevator receives this input whenever the doors reach the fully opened position. 
   • closed:  The elevator receives this input whenever the doors reach the fully closed position. 

   Your elevator has these guard conditions (and no others) available (you probably won't need both of them):

   • isClear.  This condition is true whenever the doorway is clear so that the door can close safely.  This condition comes from the clear sensor. 
   • isOpened:  This condition is true whenever the doors are in the fully opened position. 

   Your elevator must have these properties: 

   1. The doors begin to open as soon as the car stops at a floor. 
   2. The doors must remain open a minimum of 3 seconds. 
   3. The doors do not start to close until the doorway is not obstructed. 
   4. If the doors are closing and the doorway becomes obstructed, they must reopen and then remain open 10 seconds after the door reopens and the doorway becomes clear, whichever is later. 
   5. The doors must remain open 20 seconds after the extended door open button is pressed while the doors are open.  The extended door open button has no effect at any other time (unlike in most real elevators), in order to simplify your statechart. 

   Your statechart must have these actions that make these things happen at the appropriate times: 

   • "The car moves up":  The elevator car moves up to the next destination floor. 
   • "The car moves down":  The elevator car moves down to the next destination floor. 
   • "The car stops at the destination floor":  The elevator car stops at the destination floor. 
   • "The doors open":  The doors go through the process of becoming more open over some period of time.  This process may begin from a situation in which the doors are completely closed, or from a situation in which they are only partly closed. 
   • "The doors close":  The doors go through the process of becoming more closed over some period of time.  This process may end in a situation in which the doors are completely closed, or in a situation in which they are only partly closed. 

   Hint:  My solution uses a composite state, after, when, and do actions in states.  Of course, there are other ways to accomplish the same thing. 

   A sloppy solution can be done in less than half an hour, but one that is an actual statechart that if executed would act like the described elevator, as opposed to an approximation that isn't much good, will probably take at least half an hour to construct and verify.  The solution took me four hours, counting verification (and adjusting the problem to make it more manageable). 

3. FSP 32 points
   

   Consider a stoplight that cycles through green, yellow, and red, but also may go to flashing red at any time, after which it transitions to red and then back into the cycle.  • Write one or more recursive FSP processes that define a labeled transition system (LTS) for this stoplight.  The figure shows a cleaned-up version of the diagram LTSA produces for it;  you will probably want to download LTSA or run it from the web page to check your definition.  • Name the main process that pulls together all the behavior STOPLIGHT. 

   Hint:  my solution, which perhaps is structured in the most straightforward way, defines four processes including STOPLIGHT. 

4. MSCs 10 points total
   1. 2 pts • In a message sequence chart, what are the vertical lines called? 
   2. 2 pts • The vertical lines represent what?  Give both names. 
   3. 2 pts • What do you know about the time sequence of the messages that come out of or go into a particular axis? 
   4. 2 pts • What do you know about the time sequence of messages coming out of or going into different axes? 
   5. 2 pts • Is it possible to draw an "inconsistent" MSC?  • If so, how?  • If not, what about messages coming into one instance from two other instances? 
5. Testing 8 points total
   1. 2 pts • What's the difference between a test case and a test suite?
   2. 2 pts • Why don't we just test programs exhaustively? 
   3. 2 pts • Compare and contrast test effectiveness and test efficiency.  Can a test suite be both?  Can it be neither? 
   4. 2 pts • Compare and contrast black-box and white-box testing.  Is one better than the other?  Why or why not? 
6. Coverage 38 points total

   Here is a program:

    1.  int boo(int n) {
    2.    if (2 < n) {
    3.      n = 3;
    4.    }
    5.    while (0 < n) {
    6.      n -= 2;
    7.    }
    8.    if (n < 0) {
    9.      n = 0;
   10.    }
   11.    return n;
   12.  }
       

   Give minimal test sets that achieve each of the coverage criteria listed below.  For each test case in the set, • give the value for n and • state the path that the test case produces through the program (using the bold-faced statement numbers only).  • List the test sets in order by length of path (shortest first) then (for equal-length paths) alphabetically. 

   Note that when you describe a path that goes through a while or if, you must list the while or if statement each time the condition is evaluated, even if the loop or "if" is not taken:  for example, if n is 1, then the path through the program begins with 1, 2, 5, 6, 5, .... 

   1	(because n receives its value there)
   2	(because n is used to decide not to take the "if" clause)
   5	(because n is used to decide to take the loop)
   6	(because n is used and def'd, getting the value -1)
   5	(because n is used to decide to take the loop)

   1. 20 pts • Give a minimal test set that achieves all-paths coverage (as closely as can be achieved for this program — that is, all paths the program permits).  • Your test set should have five test cases. 
   2. 4 pts • Give a minimal test set that achieves all-statements coverage (but not all-paths coverage).  • Your test set should have one test case. 
   3. 14 pts • Give a minimal test set that achieves all-defs coverage.  •  List the defs (by their statement numbers) (there are four) and for each def give the uses of it that your test set covers (there should be six uses covered in total).  • Your test set should have one test case. 

      You will have to construct the data-flow graph to get the answers for this question, but you do not need to submit your graph. 

Thomas A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences