Preview

01 - Finite State Machines #1

 1. Finite state machines are a simple, intuitive way of capturing _______________.

  time-bound events

  infinite events

  real-life events

  events that are bound by functions

 2. Finite state machines are often used as a tool by programmers to _______ and formalise the operation of programs.

  complexity

  simplify

  de-commision

  delete

 3. An example of a "device" that has been designed by using finite state machines is:

  CPU

  Traffic Lights

  Analogue Clock

  Mobile phone case

 4. Finite machines can also be used as an ____________________________ to describe the operation of Turing machines.

  alarming recursive routine

  abrasive function

  abstract concept

  absorptive rule

 5. A finite state machine is described by: (which of the following apply?)
1. A set of states
2. A start state
3. Possibly a set of final states
4. Transition function/table
5. Input alphabet

  None of the listed options are valid

  Only 1,2 and 5 are valid

  Just 1,2,3 and 5 are valid

  All of the listed options are valid

 6. A finite state machine is described by an input alphabet. This defines _____________________________

  all the possible input events

  up to 2 (binary) input events

  a single input event by which means we can finitely test the system

  only the impossible input events

 7. Finite state machines can be represented graphically using:

  finite state central diagrams

  state input diagrams

  state transition diagrams

  Transition circle diagrams

 8. State transition diagrams consist of states and transitions.

  TRUE

  FALSE

 9. Generally speaking states are represented by arrows and transitions are represented by circles.

  FALSE

  TRUE

 10. A finite state machine has output but is never depicted showing the input.

  FALSE

  TRUE

 11. Finite automata are often used in the frontend of programming language compilers. Such a frontend may comprise several finite state machines that implement a ____________________

  lexical analyzer and a parser.

  CPU and RAM filament

  iterative function (usually nested)

  recursive subroutine

 12. An example of a "device" that has been designed using FSM could be a controller that opens an automatic door.
Regulation would be required to control when the door opens and when it shuts
finite_state_machines_1.png

  FALSE

  TRUE

 13. In this diagram, the states have been encoded using _________________________. The sensors have also been encoded using _____________.
finite_state_machines_2.png

  on bits (1s)

  boolean variables

  local variables

  a single bit

 14. Have a look at the following formula for a door controller. Which of the following statements is likely to be true (with FSM in mind)

  None of the listed options are valid answers.

  The input (current state) depends on the current state

  the input (next state) depends on the current state

  The output (next state) depends on the current state

 15. Suppose you were given the example of a vending machine. What would you do first to convert this FSM to a circuit?

  Determine a boolean expression that defines the transition of states and put it in a table

  Determine an encoding for the transition function and create the states as local constants

  Determine an encoding for the states and create boolean expressions for the transition function

  Determine an encoding for the boolean expression and then create a transition table