引言

什么是形式语言

经过数学公式定义的语言，具有严格的语法规则。

什么是自动机理论

1. 研究抽象机器所能研究的问题
2. 自动机：抽象的识别形式语言的机器，知识分析抽象工具的抽象机器，不具有实际的物质形态。
3. 主要内容
   1. 有限状态机
   2. 下推状态机
   3. 图灵机
4. 课程内容
   1. 正则语言
      1. 有穷自动机
      2. 正则表达式
      3. 正则语言的性质
   2. 上下文无关语言
      1. 上下文无关语法
      2. 下推自动机
      3. 上下文无关语言的性质
   3. 计算导论
      1. 图灵机以及扩展

为什么学形式语言与自动机

1. 编程语言也是一种形式语言
2. 正则表达式在许多地方有所应用
3. 面试内容经常有包括

基本概念

1. **字母表：**字符的非空有穷集

   1. $\Sigma_1 = \{0, 1\}$
   2. $\Sigma_2=\{a,b,\dots,z\}$
   3. $\Sigma_3=\{x|x\text{是一个汉字}\}$

2. **字符串：**由某字母表中的符号组成的有穷序列

   1. 对$\Sigma_1$，$0,01,1,10,111,000$都是$\Sigma_1$上的字符串
   2. $\varepsilon$为对任意字母表的空串

3. 一般约定

   1. 字母表：$\Sigma,\Gamma$
   2. 字符：$a,b,c$
   3. 字符串：$w,x,y,z$
   4. 集合：$A,B,C$

4. 字符串长度

   对字母表$\Sigma$，递归定义为

   $$ |w| = \begin{cases}0&,w=\varepsilon \\ |x| + 1 &,w=xa\end{cases},a\in \Sigma;w,x\text{是}\Sigma\text{中字符组成的字符串} $$

5. 字符串的连接：$x\cdot y$或者$xy$

   对字母表$\Sigma$，递归定义为

   $$ xy=\begin{cases} x &, y = \varepsilon \\ (xz)a&, y = za\end{cases},a\in\Sigma;x,y,z\text{都是字符串} $$

   对任何字符串，有$\varepsilon x = x\varepsilon = x$

6. **字符串的幂：**递归定义为

   $$ x^n=\begin{cases}\varepsilon &,n=0\\x^{n-1}x&,n>0\end{cases} $$