前言
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, ab11 \}$
集合 $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 \}$
語言唯一的限制就是所有字母表都是有限的