语言

字母表

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

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

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

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

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

指向原始笔记的链接

符号: 字母表中的元素

字符串

字母表 中符号组成的有限序列.

串的长度 $|abcde|=5$

串的链接 $(abc)\ast (de)=abcde$

串的反转 $(abcde{)}^R=edcba$

指向原始笔记的链接

空词

长度为 0 的串, 记为 $\epsilon$.

指向原始笔记的链接

给定字母表上一些字符串的集合称为语言.