Powers of an Alphabet

• Definition: Given an alphabet $\sum$ (a finite set of symbols), the $k$-th power of $\sum$ is the set of all strings of length $k$ formed from symbols in $\sum$.
• Notation: ${\sum }^k$
• Special Cases:
  • ${\sum }^0=\{\epsilon \}$
  • ${\sum }^1=\sum$
  • ${\sum }^2=ab|a,b\in \sum$
• Extension:
  • ${\sum }^{\ast }={\cup }_{n=0}^{\infty }{\sum }^n\to$ all finite strings over $\sum$. Also called the Kleene Star.
  • ${\sum }^{+}={\cup }_{n=1}^{\infty }{\sum }^n\to$ all non-empty string over $\sum$.
• Example: If $\sum =\{a,b\}$:
  • ${\sum }^0=\{\epsilon \}$
  • ${\sum }^1=\{a,b\}$
  • ${\sum }^2=\{aa,ab,ba,bb\}$
  • ${\sum }^{\ast }=\{\epsilon ,a,b,aa,ab,ba,bb,aaa,\dots \}$