Alphabet

A finite set of symbols. Denoted by $\Sigma$.

String

A finite sequence of symbols from $\Sigma$. Length of string $x$ is denoted by $|x|$.

Null String

String with length 0. Denoted by $\Lambda$.

Concatenation

Concatenation of strings $x$ and $y$ is $xy$. Associative.

Repetition

$a^k$ means symbol $a$ repeated $k$ times. $a^0 = \Lambda$.

$\Sigma^k$ is the set of all k-length strings from symbols of $\Sigma$. $\Sigma^0 = \{\Lambda\}$.

Substrings

A string found inside another string.

• Prefix
  Initial substring.
• Suffix
  Final substring.

Σ-Star

Set of all strings over $\Sigma$.