引言
Sometimes it’s the people who no one imagines anything of who do the things that no one can imagine
最近从毕导视频弹幕中得知关于图灵的记录片 The Imitation Game(模拟游戏)，顺便看了一下，对于片中出现的该句话感触颇深，以此当作形式语言与自动机文章的开篇题引
当您开始有点抑郁的时候，也请看看 Amy 关于此句的感悟吧
基本概念
字母表：符号 (字符) 的非空又穷集
\[{\textstyle \sum_1} = \{0, 1\}\]字符串：由某字母表中符号组成的有穷序列
\[若 \space {\textstyle \sum_1} = \{0, 1\}，那么 \space 0，1，00，101011 \space 为 \space {\textstyle \sum_1} \space 上的字符串\]空串：记为 $\varepsilon$ ，有 0 个字符的串。对任意字母表 $\sum$ 都有 $\varepsilon \notin \sum$
符号的使用约定
字母表：$\sum, \Gamma, \cdots$
字符：$a, b, c, \cdots$
字符串：$\cdots,w,x,y,z$
集合：$A,B,C,\cdots$
字符串的长度：字符串中符号所占位置的个数
\[对于 \space {\textstyle \sum_1} = \{0, 1\}，|0010|=4\]字符串 $x$ 和 $y$ 的连接：将首尾相接得到新字符串的运算，记为 $x \cdot y$ 或 $xy$
\[x=01, y=ab, 则 \space xy=01ab\]字符串 $x$ 的 $n$ 次幂 ($n \ge 0$) ，递归定义为
\[x^n= \left \{ \begin{matrix} \varepsilon & n=0 \\ x^{n-1}x & n \gt 0 \end{matrix} \right .\]$对于 \space {\textstyle \sum_1} = {a, b} (ba)^2=baba, ba^2=baa$
集合 $A$ 和 $B$ 的连接，记为 $A\cdot B$ 或 $AB$ ，定义为
\[A \cdot B = \{ w |w=x \cdot y, x \in A \space and \space y \in B \}\]若 $\space A = {0, 11} \space B = {ab, ba} $
$AB = { 0ab, 0ba, 11ab, 11ba }, BA= { ab0, ab11, ba0, ba11 }$
集合 $A$ 的 $n$ 次幂 ($n \ge 0$) ，递归定义为
\[A^n= \left \{ \begin{matrix} \{ \varepsilon \} & n=0\\ A^{n-1}A & n \ge 1 \end{matrix} \right .\]$对于 \space {\textstyle \sum_1} = {0, 1} $，有 ${\textstyle \sum^0}={\varepsilon}, {\textstyle \sum^1}={0,1}, {\textstyle \sum^2}={00,01,10,11}, \cdots$
克林闭包 (Kleene Closure) : 将某字母表的所有幂 (包含零次) 去并集得到
\[{\textstyle \sum^*} = \bigcup_{i=0}^{\infty}{\textstyle \sum^i}\]正闭包 (Positive Closure) : 将某字母表的所有幂 (不包含零次) 去并集得到
\[{\textstyle \sum^+} = \bigcup_{i=1}^{\infty}{\textstyle \sum^i}\]显然
\[{\textstyle \sum^*} = {\textstyle \sum^+} \cup \{ \varepsilon \}\]语言
定义：若 $\sum$ 为字母表且 $\forall L \subseteq \sum^*$ ，则 $L$ 称为字母表 $\sum$ 上的语言
- 自然语言、程序设计语言等
- $ \{ 0^n 1^n \mid n \ge 0 \} $
- The set of strings of 0’s and 1’s with an equal number of each
- $\emptyset$ ，${ \varepsilon }$ 和 $\sum^*$ 分别都是任意字母表 $\sum$ 上的语言，但 $\emptyset \ne { \varepsilon }$
语言唯一的约束就是所有字母表都是有穷的