关于自动机

自动机理论研究抽象计算装置或“机器”，因为某个叫后缀自动机的东西和编译原理，就来康康这是啥。 一些贯穿自动机理论的概念 字母表 “字母表”是符号的有穷非空集合， 通常使用$\Sigma$表示。 例如： $\Sigma$ = {0, 1}, 二进制字母表。 $\Sigma$ = {a, b, …, z}, 所有小写字母集合。 串 “串”（或者单词）是从某个字母表中选择符号的有穷序列。 例如：010101是从$\Sigma$ = {0, 1} 中选出的串。 空串：是出现0次符号的串，记作$\varepsilon$。它是可以从任何字母表中选择的串。 串的长度：定义$\Sigma^k$是长度为$k$的串的集合，标准记号为$|w|$，$|\varepsilon|=0$ 。 字母表的幂：定义$\Sigma^k$为长度为$k$的串的集合，串的每个符号都属于$\Sigma$ 。字母表的所有串的集合约定记为$\Sigma^*$ 。 语言 $\Sigma$是某个具体的字母表，全都从$\Sigma^*$中选出的串的一个集合称为“语言”。如果$\Sigma$是字母表，且$L\subseteq\Sigma^*$，则$L$是$\Sigma$上的语言。 问题 一个“问题”就是判定一个给定的串是否属于某个具体语言的提问。...