# 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.

FALSE

TRUE

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

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.

TRUE

FALSE

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``` 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.

TRUE

FALSE

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.

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 ___________________. 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.` 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.

FALSE

TRUE

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.

TRUE

FALSE

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

FALSE

TRUE