Preview

03 - Transition function and state transition diag

 1. In reference to a Turing machine, an alphabet refers to acceptable symbols for a given turing machine.

  TRUE

  FALSE

 2. The start state is the initial state of the Turing machine.

  TRUE

  FALSE

 3. Select the term that this definition matches.
Method of notating how a Turing machine 
moves from one state to another and how 
the data on the tape changes

  Turing function rule

  State transition diagram

  Transition function/rule

  Turing state rule

 4. Select the term that this definition matches.
Visual representation of the transition
 function of a Turing machine

  Transition function/rule

  Universal machine

  State transition diagram

  Instruction table

 5. Select the term that this definition matches.
Method of describing a Turing
machine in tabular form

  Instruction table

  Universal machine

  State transition diagram

  Transition function/rule

 6. Select the term that this definition matches.
Machine that can simulate a Turing 
machine by reading a description of 
the machine along with the input of its own tape

  Universal machine

  Instruction table

  State transition diagram

  Transition function/rule

 7. Objects change their state in response to ________________________.

  identical objects

  dissimilar objects that they collide with

  events and to time

  other objects that mirror their behaviour

 8. It is a __________________ that captures a change to the objects state.

  Universal machine

  Transition function/rule

  State transition diagram

  Instruction table

 9. A state diagram is also referred to as a state machine or statechart

  TRUE

  FALSE

 10. A state diagram shows the states of a _____________.

  series of objects

  instruction table

  single object

  series of classes

 11. A state is represented as a _____________________.

  series of three dots on a transition diagram

  rounded rectangle on a transition diagram

  square or diamond on a transition diagram

  triangle on a state diagram

 12. When using Turing machines, state transition diagrams and their associated transition rules can be expressed as ____________.

  transition function

  turing functions

  ruled symbol functions

  state functions

 13. This Turing machine adds two unary numbers by removing the first 1 and then moving it to the next space. It then _______________________________________.
transitionrules_1_modelsofcomputation.png

  moves the 1 to the very start space

  enters a 1 into the next available space and then replaces the next slot with a 0

  moves the pointer along to the every end

  moves the pointer back to the start of the number

 14. The first line of the transition rules shown here (relating to the diagram above) means: if we are on state 1, and receive a 1, then write a square to the tape and __________________.
transitionrules_relatingtodiagram.png

  move the read head right and then back again, replacing the element in state 1 with a new input

  move the read head right, finally moving to state 2

  move the read head left, remaining in state 1 until the input is 0

  move the read head right, until the last available empty space is found (e.g. an infinite state)

 15. Read the excerpt below. The Turing machine below is in S0, with the read/write head over the square pointed to by the arrow. Which direction does the head move first?
Consider this Turing machine with the following transitions (transitions are in the order: current state, input symbol, next state, output symbol/move):  
(
state_transition_diagram_1.png

  Right

  It would stay in the same place

  Left

  It would move down

 16. How many moves would the head make before it actually writes a symbol?

  6

  4

  2

  8

 17. What happens if the machine is in S1 and reads in a Ø?

  The Turing machine would go into an infinite loop

  The Turing machine would halt

  The Turing machine would output a 1

  The Turing machine would require additional input and therefore the head would move left

 18. Assuming numbers are coded in such a way that 1 = 0, 11 = 1, 111 = 2, 1111 = 3 etc. what is the purpose of this Turing machine?

  It decides if the second number is greater than the first

  It adds the first number to the second

  It subtracts the second number from the first

  It subtracts the first number from the second and then adds them

 19. A FSM can recognize only regular expressions. A stack machine can recognize context-free languages,

  TRUE

  FALSE

 20. Finite automaton requires memory which is why it is possible for it to remember the next state as well as its current state.

  TRUE

  FALSE