Preview

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.

  TRUE

  FALSE

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

  on and off

  boolean off and boolean true

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

  There can only be a single state in a FSM

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

  break down the problem into smaller parts of the same problem

  demonstrate the behaviour clearly

  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.

  FALSE

  TRUE

 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:

110011001
001110011
finitestatemachine2_2.png

  switch it off

  switch it to S2 (for good)

  switch it back to S1.

  switch it back to a 0

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

  FALSE

  TRUE

 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?
finitestatemachine2_3.png

  The FSM decrements the input number

  The FSM computes 2s complement of the input string

  The FSM computes the 1s complement of the input string

  The FSM increments the input number

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

  FALSE

  TRUE

 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 ___________________.
finitestatemachine2_4.png

  A moves it also to state 3

  B moves it back to state 1

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

  B moves it to state 3

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

  transition table flow chart

  state data flowchart

  state transition diagram

  transition flowchart

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

  creating state

  accepting state

  finishing 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.
finitestatemachine2_6.png

  Answer: 11001

  Answer: 01011

  Answer: 00011

  Answer: 01110

 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.

  TRUE

  FALSE

 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.

  FALSE

  TRUE

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

  TRUE

  FALSE


Report an error