02 - Finite State Machines #2

 1. A finite state machine is a form of abstraction because it models the behaviour of a system by showing states and transitions.



 2. An example of a FSM: Consider a lift (elevator). What are the possible states of the system?

  There can only be a single state in a FSM

  static on floor 1, moving up, static on floor 2, moving down, etc.

  boolean off and boolean true

  on and off

 3. Representing a system as a finite state machine is very powerful because the model allows us to ________________________________.

  demonstrate the behaviour clearly

  break down the problem into smaller parts of the same problem

  represent every detail of the system, thereby illustrating the complexity

  recursively adapt the problem

 4. Applications of finite state machines are found in many sciences. Mainly engineering, biology and most commonly in linguistics, where they are used to describe languages.



 5. Read the excerpt below and in relation to the diagram, fill in the blanks.
In this diagram, we can see that it starts in state S1, 
an input of 1 will keep it in state S1, and an input of
0 will move it to state S2. 

Once in S2 an input of 1 
will keep it there, and an input of 0 will 

This means that the following 
inputs are valid:


  switch it back to a 0

  switch it to S2 (for good)

  switch it back to S1.

  switch it off

 6. A Mealy machine does not output values where as a finite state automaton does output values.



 7. The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which of the following is true?

  The FSM decrements the input number

  The FSM increments the input number

  The FSM computes the 1s complement of the input string

  The FSM computes 2s complement of the input string

 8. Finite state automatons are unique in that they have stable and definite outputs.



 9. For example, the finite state machine in the diagram has three states. If the machine is in state 1 then an A moves it to state 2 and a ___________________.

  B moves it to state 3

  B moves it back and forth between state 1,2 and 3

  B moves it back to state 1

  A moves it also to state 3

 10. A _____________________ is a method of graphically representing finite-state machine.

  state data flowchart

  transition flowchart

  state transition diagram

  transition table flow chart

 11. Many FSMs have a final state known as the ___________________. This is indicated by a double circle.

  finishing state

  creating state

  accepting state

  finite state

 12. The sequence baaaba would produce 100010 as the output. The sequence ababb would produce _______as the output.
Some FSMs produce output. These are identified by looking for two values seperated by a / symbol.

  Answer: 01011

  Answer: 01110

  Answer: 11001

  Answer: 00011

 13. Many communications protocols, such as USB can be defined by a finite state machine‚Äôs diagram showing what happens as different pieces of information are input.



 14. You can build a finite state machine that can recognize palindromes and as it can count infinitely, it would be able to recognize all palindromes.



 15. A finite state machine can not only count but count for an infinite number (e.g. never stop)