4.2 and 4.3 Regular & Context Free Languages

A-Level Computer Science

Finite State Machine

A model of computation consisting of a finite number of states, an initial start state, and transitions between states based on input symbols.

Mealy Machine

A type of finite state machine that generates an output determined by its current state and the current input symbol.

State Transition Diagram

A directed graph visual representation of a finite state machine showing states as nodes and transitions as labeled arrows.

State Transition Table

A tabular grid showing the next states and outputs of a finite state machine based on the current state and input.

Set

An unordered collection of distinct values in which each value occurs at most once.

Set Comprehension

A compact mathematical notation used to construct a set by specifying a rule or condition that its members must satisfy.

Empty Set

A unique set that contains no elements, denoted by empty curly braces or the symbol Ø.

Finite Set

A set whose elements can be counted off by natural numbers up to a particular final element.

Infinite Set

A set with an endless number of elements that cannot be fully counted by a single finite number.

Countably Infinite Set

An infinite set whose elements can be put into a one-to-one correspondence with the set of natural numbers.

Cardinality

A property representing the total number of elements contained within a finite set.

Cartesian Product

The set of all ordered pairs formed by combining an element from a first set with an element from a second set.

Subset

A relationship where every element of a first set is also a member contained within a second set.

Proper Subset

A relationship where a first set is a subset of a second set, but the second set contains at least one element not present in the first.

Set Membership

An operation checking whether a specific value exists as an element within a given set.

Set Union

An operation combining all unique elements from two or more sets into a single new set.

Set Intersection

An operation that finds and returns only the elements common to all given sets.

Set Difference

An operation that yields a new set containing elements that belong to a first set but not to a second set.

Regular Expression

A way of describing a regular language by specifying patterns used for convenient string manipulation and text matching.

Metacharacter

A special character in regular expressions that defines a structural rule rather than a literal character, such as an asterisk, plus sign, or question mark.

Regular Language

A category of language that can be completely represented by a regular expression or accepted by a finite state machine.

Backus-Naur Form

A formal syntax notation technique used to express the production rules of a context-free grammar or programming language.

Syntax Diagram

A visual flowchart representation of production rules used to validate the syntax of a language sentence.

Context-Free Language

A category of language that can be described by Backus-Naur Form but cannot be fully represented by regular expressions alone due to nested structures.