自动机理论-中心概念

字母表

符号的有穷非空集合。用$\Sigma$表示字母表。

串

从某个字母表中选择的符号的有穷序列。

• 空串：记作$ϵ$
• 串$w$的长度记为$|w|$
• 字母表的幂：${\Sigma }^k$是长度为$k$的串的集合
• 字母表上所有的串的集合记作${\Sigma }^{\ast }$
• 字母表上非空串的集合记作${\Sigma }^{+}$
• 串的连接：$xy$表示$x$和$y$的连接

语言

全都从 ${\Sigma }^{\ast }$ 中选出的串的一个集合称为语言。

• 何时 $L^{+}=L^{\ast }-\{ϵ\}$？$ϵ\notin L$

问题

判定一个给定的串是否属于某个具体语言的提问。