Finite State Machines / The Turing Machine

Question 1

What is a finite state machine and why are they useful?

Answer 1

• An abstract model that has a finite number of states and can only be in one state at a time
• They’re useful for recognising logical sequences
• They can model a range of problems simply

Question 2

What is a finite state machine with no output called?

Answer 2

A Finite State Automaton (FSA)

Question 3

What is a state transition diagram?

Answer 3

A visual representation of a FSM

uses circles and arrows

Question 4

How is a state represented in a FSM?
How is a transition function represented in a FSM?
How is the starting state represented in a FSM?
How is the target state represented in a FSM?

Answer 4

A state is represented by a circle and a name that identifies it : S0, S1, S2 …
A transition is represented by an arrowed line and the input that makes this transition: 0, 1 or A, B, C, D
The starting state is represented with an arrow pointing towards it
The target state has a double circle around the name that identifies it

Question 5

What is a state transition table?

Answer 5

It records all the states and transitions possible for a specific FSM

Question 6

What is a mealy machine?

Answer 6

• A mealy machine is a finite state machine whose output is determined by its current state and the current input.
• no more than one transition is possible at a time

Question 7

How does a mealy machine show what the inputs and outputs are?

Answer 7

Along the transition line it will show two characters or digits : a/b. a is the input and b is the output. a and b can be anything from a number to a letter to a word.

Question 8

What can mealy machines represent?

Answer 8

Can represent electronic circuits and bitwise operations.
Can carry out an XOR function
They have a range of uses such as traffic light control and vending machines.

Question 9

Describe the Halting problem

Answer 9

It determines if a program will halt (1 mark)

For a specific input (1 mark)

Question 10

Why is it not possible to create a Turing machine that solves the Halting problem?

Answer 10

The Halting problem is non-computable, there is no algorithm that solves the Halting problem

Question 11

State three components of a Turing machine.

Answer 11

• The finite alphabet of symbols that it can use
• Infinite tape
• Finite set of states
• A set of transition rules;
• A read-write head
• Start state
• an accepting / halting states

Question 12

Explain what a Universal Turing Machine is.

Answer 12

• Instructions for TM and the TM’s input are stored on the UTM’s tape
• A Turing machine that can execute the behaviour of any other Turing machine // can compute any computable sequence

Question 13

Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?

Answer 13

Because it has an infinite amount of memory/tape;

Question 14

What are transition rules?

Answer 14

Rules that describe what a finite state machine should do given certain input.

Question 15

What do mealy machine state diagrams not have?

Answer 15

A target state

Question 16

What can mealy machines be used for?

Answer 16

They can provide a simple model for:

• Cipher machines.
• Traffic lights
• Timers
• Vending machines
• Basic electronic circuits

Question 17

What does the Turning machine consist of?

Answer 17

• An infinitely long strip of tape divided into squares
• A read/write head
• A halting state/stop state

Question 18

What does a square represent in a Turing Machine?

Answer 18

A square represents a blank state

Question 19

What notation is used by Turing machines?

Answer 19

(input, output, movement) is used.
for example (1,1,L) means if the input is 1, output 1 and move left

Question 20

How do Turing machines work?

Answer 20

They find the first blank cell on the tape, to the right of the current position of the read/write head.

Question 21

What is a transition function?

Answer 21

The transition rules for a Turing Machine

Question 22

What is the notation for a transition rule in a Turing machine?

Answer 22

δ (Current State, Input symbol) = (Next State, Output symbol, movement)
For example:
δ (S1, 0) = (S2, 1, L) means IF the current state is S1 and the input is 0, then write a 1 on the tape, move left and change state to S2

Question 23

What can a Turing machine represent?

Answer 23

A Turing machine can theoretically represent any computation

Question 24

What idea did the Universal Turing Machine lead to and why was this?

Answer 24

• The stored program computer
• Because a Turing Machine reads (off it’s own tape) both the description of the machine to be simulated and the input to the machine.

Question 25

What must a valid identifier consist of in a FSM?

Answer 25

• Must start with a lowercase letter
• Any number of letters or numbers may follow after this
• There is no limit on the length of a identifier

Question 26

What is a dead state

Answer 26

A state that once arrived in, can never reach the accept state