Systems Analysis and Synthesis

3.13. Exercises

1. Consider Figure 3.9, which shows an FSA for books in a library. Sketch the figure and modify it to include an additional state, On Hold, and two additional events. Books can be placed On Hold by a Hold event when they are in any of the states On Loan, Shelved, or Archived. A book in the On Hold state can become On Loan as the result of a Lend event.

2. Consider the DFA of Figure 3.7, which detects if the last letter but one of a binary sequence is ‘1’. By analogy, how many states would you expect a DFA that detects if the last letter but two of a binary sequence is ‘1’? How many states would you expect the DFA to have in order to detect if the last letter but n of a binary sequence is ‘1’? What does this tell you about the tractability ...