Languages

Alphabets and Strings

• Alphabet → finite, nonempty set $\Sigma$ of symbols
• Strings → finite sequences of symbols from the alphabet
  • If the alphabet $\Sigma = \{a,b\}$, then $abab$ and $aaabbba$ are strings on $\Sigma$.

<aside> ℹ️ We will use lowercase letters $a, b, c, \dots$ for elements of $\Sigma$ and $u, v, w, \dots$ for string names.

</aside>

• If $w$ is a string, then $w^n$ stands for the string obtained by repeating $w$ $n$ times.

We have the special case $w^0 = \lambda$ (empty string) for all $w$.

Star-Closure of Alphabet

$\Sigma^*$ denotes the (infinite) set of strings obtained by concatenating zero or more symbols from $\Sigma$.

• $\Sigma^*$ always contains the empty string $\lambda$.
• $\Sigma^+ = \Sigma^* - \{\lambda\}$ is used to exclude the empty string.

A language is defined very generally as a subset of $\Sigma^*$.

Set Operations on Languages

Languages are sets; the union, intersection, and difference of two languages are immediately defined.

• Complement → $\overline{L} = \Sigma^* - L$
• Reverse → $L^R = \{ w^r : w \in L \}$
• Concatenation → $L_1L_2 = \{ xy : x \in L_1, y \in L_2 \}$
  • $L^n$ is $L$ concatenated with itself $n$ times, with special cases $L^0 = \{\lambda\}$ and $L^1 = L$.
• Star-closure → $L^* = L^0 \cup L^1 \cup L^2 \cdots$