Computer Science - Paper 2 FSMs

Finite State Machines

Any device that can store its current state and can change state based on an input

Mealy Machine

A FSM with outputs

Turing Machine

A FSM with the ability to read and write data to an unlimited tape

Transition Function

A set of rules defining the behaviour of a Turing machine

Universal Machine

Can simulate any turing machine by take its tape as an input

Regular Language

A language that can be represented using regular expressions 

Regular Expressions

Contain strings of characters that can be matched to the content of a set, allowing you to find patterns in data

Set

A collection of data that is unordered and contains each item at most once 

Context-free Languages

An unambiguous way of describing the syntax of a language where the syntax is complex

Backus Naur Form

A form of notation for describing the syntax used by a programming language

Set Comprehension/Building

The process of creating sets by describing them using notation rather than listing elements

Empty Set

Could contain something but it doesn't, it has no elements

Countably Infinite Sets

Sets where elements can be put in correspondence with the set of natural numbers 

Cartesian Product

Combining the elements of two or more sets to create a set of ordered pairs

Proper Subset

All the elements of one set are also contained within another set

Improper Subset

Two sets are exactly the same, where one can be said to be subsets of on another