Sets

A set is an unordered collection of distinct elements. In computer science, sets underpin formal language theory.

Set notation

• ∈ — element of: 3 ∈ {1,2,3}
• ∉ — not element of: 4 ∉ {1,2,3}
• ∅ — empty set (no elements): {}
• ⊆ — subset: A ⊆ B means every element of A is in B
• ∪ — union: elements in A or B (or both)
• ∩ — intersection: elements in both A and B
• |A| — cardinality: number of elements in A
• A* — Kleene star: zero or more concatenations of elements from A

Cardinality examples

A = {a, b, c}   |A| = 3
B = {}          |B| = 0  (empty set)
C = {1,2,3,4}   |C| = 4

Languages and Alphabets

In formal language theory:

• Alphabet (Σ) — a finite set of symbols: e.g. Σ = {0,1} for binary
• String — a finite sequence of symbols from Σ: e.g. "011"
• Empty string (ε) — a string of zero characters
• Language — a set of strings over Σ: e.g. the language of even-length binary strings
• Σ* (Sigma-star) — the set of ALL strings over Σ, including ε (Kleene star)

Regular Expressions

A regular expression (regex) is a compact notation for defining a regular language (the class of languages recognised by FSMs).

Core regular expression operators

Examples

// All binary strings ending in 1:
(0|1)*1

// Strings of one or more a's followed by one or more b's:
a+b+

// All strings over {a,b}:
(a|b)*

// Binary strings of even length:
((0|1)(0|1))*

// Valid simple email pattern (simplified):
[a-z]+@[a-z]+\.[a-z]+

Regular Languages

A regular language is any language that can be:

• Described by a regular expression
• Recognised by a finite state machine (FSM/DFA)
• Generated by a regular grammar

These three representations are equivalent — they all describe exactly the same class of languages.

Regular vs non-regular languages