字母表

任意一个有限集, 记为 $\Sigma ,\Gamma$.

$\Sigma$ 上的所有有限长串记为 ${\Sigma }^{\ast }$.

$\Sigma$ 上的任意长串都是 ${\Sigma }^{\ast }$ 的子集.

$\Sigma$ 上所有无限长串记为 ${\Sigma }^N$.

$\Sigma$ 上的语言与 ${\Sigma }^N$ 一一对应.