Notation¶

Greek alphabet¶

Notation	Meaning
\(w\)	String made of symbols from \(\Sigma\)
\(w^R\)	String obtained by writing \(w\) in the reverse order
\(\mid w\mid\)	Length of the string \(x\)
\(xy\)	String made by concatenating \(x\) and \(y\)
\(w^n\)	String made by concatenating \(n\) copies of \(w\): \(\underbrace{ww\ldots w}_{n \text{ copies}}\)
	In particular: \(w^0=\varepsilon\), \(w^1=w\) and \(w^2=ww\)
\(\{0,1\}^n\)	Binary strings of length exactly \(n\) symbols
\(\{0,1\}^*\)	Binary strings of any length: \(\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}\)

The symbol \(■\) is just a place holder.

Notation	Meaning
\(■ + ■\)	Union ("or")
\(■\,■\)	Concatenation ("gluing" two strings) (juxtaposition/no symbol)
\(■^*\)	Star (zero or more copies) e.g. \(1^*=\{\varepsilon,1,11,111,1111,\ldots\}\)
\(■^+\)	One or more copies -- shorthand for \(■\,■^*\) e.g. \(1^+=\{1,11,111,1111,\ldots\}\)
\(\Sigma^*\)	Any string of finite length over the given alphabet, including \(\varepsilon\) (zero length)
\(\Sigma^+\)	Any string of finite non-zero length over the given alphabet (not \(\varepsilon\))
\(()\)	Grouping, to override usual precedence rule: star, concatenation, union
\(\varepsilon\)	Empty string
\(\emptyset\)	No strings at all

Notation	Meaning
\(\{{\textcolor{gray}{x_1,\ldots,x_n}}\}\)	Finite set consisting of the elements \(x_1\) until \(x_n\)
\(\{{\textcolor{gray}{pattern}} \mid {\textcolor{gray}{condition}}\}\)	Set of items matching \(pattern\) and satisfying \(condition\).
	The "\(\mid\)" symbol is read "such that"
\(\emptyset\)	Empty set, i.e. \(\{\}\)
\(\in\)	"in", member of a set
\(\notin\)	"not in", not a member of a set
\(\cup\)	Union of two sets
\(\cap\)	Intersection of two sets
\(-\)	Difference of two sets
\(\times\)	Cartesian product of two sets
\(\subset\)	Subset of ...
\(\mid A\mid\) or \(\#A\)	Cardinality of the set \(A\), i.e. count of its elements
\(2^A\)	Power set of \(A\), i.e. set of all subsets of \(A\)
\(\land\)	Logical "and"
\(\lor\)	Logical "or"
\(\lnot\) or \(\bar{\textcolor{gray}{■}}\)	Logical "no"
\(\oplus\)	Logical "xor" -- "exclusive or"

Notation	Meaning
\(\mathbb{N}\)	Natural numbers: \(\{1,2,3,\ldots\}\)
\(\mathbb{Z}\)	Integers: \(\{0,1,-1,2,-2,3,-3,\ldots\}\)
\(\mathbb{Z}_{\geq 0}\)	Non-negative integers: \(\{0,1,2,3,\ldots\}\)
\(S'\)	A set called "\(S\) prime" (a way of making new names)
\(S''\) or \(S'''\)	A set called "\(S\) double prime" / "\(S\) triple prime"

Notation	Meaning
\(=\)	equals
\(\neq\)	not equal
\(<\)	less than
\(\leq\)	less than or equal
\(>\)	greater than
\(\geq\)	greater than or equal
\(n!\)	Factorial of \(n\): \(n\times(n-1)\times (n-2)\times \cdots \times 2 \times 1\)