AQA A2 Computing 1.3 Finite State Machines

Question 1

Finite state machine (FSM)

Answer 1

consists of a set of symbols (input symbol alphabet) and if it produces output, a set of output symbols (output symbol alphabet), a finite set of states and a transition funtion that maps a state-symbol pair (current state and input symbol) to a state (next state) and possibly generates an output (output symbol) depending on the type of FSM.

Question 2

Transition function

Answer 2

maps (input symbol, current state) to (output symbol, next state)

Question 3

Transition table

Answer 3

tabulates the mappings (input symbol, current state) to (output symbol, next state)

Question 4

Deterministic finite state ,machine

Answer 4

an FSM that has just one next state for each pair of state and input symbol.

Question 5

Non-deterministic finite state machine

Answer 5

an FSM that may have several possible next states for each pair of state and input symbol.

Question 6

Halting state

Answer 6

a state that has no outgoing transition

Question 7

Mealy machine

Answer 7

an FSM that determines its outputs from the present state and from the inputs

Question 8

Moore machine

Answer 8

an FSM that determines its outputs from the present state only

Question 9

Finite state automation (FSA)

Answer 9

an FSM that produces no output while processing the input but which responds YES or NO when is has finished processing the input. Also called a finite automaton.

Question 10

Turing machine

Answer 10

an FSM that controls on or more tapes where at least one tape is of unbouned length (i.e. infinitely long).