AQA AS Level Computer Science: Finite State Machines

This set of flashcards covers the definitions, graphical and tabular representations, types (Automata vs. Mealy), and practical applications of Finite State Machines based on AQA AS Level Computer Science Unit 2.

Finite State Machines (FSMs)

A model of computation used to understand how computers work, consisting of a set number of states and transitions between them based on inputs.

Finite State Automata

A type of finite state machine with no output, where the validity of an input sequence is determined by whether it ends in an accept state.

Mealy machines

A type of FSM that generates outputs on each transition and has no particular end state; the output depends on both the current state and the current input.

State Transition Diagram

A graphical way of presenting finite state machines, using notation for start states, transitions, and accept states.

State Transition Table

A tabular representation of a finite state machine that lists the current state, input, and the resulting new state.

Accept State

The final state in an FSM indicating that an input sequence is valid; it is typically represented by a double-circle notation.

Trap State

A state within a finite state machine, such as $S3$ in specific examples, whose purpose is to capture and hold invalid inputs.

Formal Verification

The mathematical analysis of FSMs to ensure correctness, which is crucial in safety-critical systems.

State Minimisation

A feature of Mealy machines that often allows for fewer states than Moore machines to achieve the same logic.

Immediate Reaction

A characteristic of Mealy machines where the output updates during the transition itself rather than after reaching a new state.

Mealy Machine Transition Notation (e.g., 0/1)

A notation where the first value represents the input and the second value represents the output (for instance, input is $0$, output is $1$).

Vector Angle Formula

$\cos(\theta) = \frac{\tan(\theta)}{|\text{a}| \times |\text{b}|}$ as used in the starter activity to calculate the angle between two vectors.

Wash State

A state in a washing machine FSM where the machine fills with water, adds detergent, and agitates clothes.

Rinse State

A state in a washing machine FSM where dirty water is drained and the drum is refilled with clean water.

Spin State

A state in a washing machine FSM where the drum rotates at high speed to remove water.

Done State

The final state in a washing machine FSM indicating the cycle is complete and ready for unloading.