Skip to content

Notation

Greek alphabet

Symbol Name Common use
\(\Sigma\) Sigma Set of alphabet symbols
\(\Gamma\) Gamma Set of stack/tape symbols
\(\alpha\) alpha
\(\beta\) beta
\(\gamma\) gamma
\(\delta\) delta Transition function
\(\varepsilon\) epsilon Empty string
\(\sigma\) sigma

Strings

Notation Meaning
\(\varepsilon\) Empty string (Length = 0)
\(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\}\)

Regular expressions

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

Sets and logic notation

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"

Numeric

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\)