计算理论的核心问题：计算机的基本能量和限制是什么

• 可计算性：哪些问题可以通过计算解决
• 计算复杂性：解决可计算的问题需要多少资源
• 自动机理论：为了研究计算，要使用哪些计算模型
  • 图灵机
  • 有限状态机
  • 文法、下推自动机

形式语言定义

• 符号$a$、$b$、$c$、......
• 字母表$\Sigma$、$\Gamma$、......：符号的非空集合
• 字符串$w$、$x$、$y$、......：由字母表中的符号组成的有穷序列
• 空串$\varepsilon$：有0个字符的字符串

字符串的连接$xy$：字符串首尾相接得到新字符串

递归地定义字符串的连接：

$xy=\left\{ \begin{aligned} x&&y=\varepsilon\\ (xz)a&\quad&y=za\\ \end{aligned} \right.$

其中，$a\in\Sigma$、$x$、$y$、$z$是$\Sigma$中的符号组成的字符串。

含义：

• 字符串与空串的连接等于其自身
• 如果字符串$y$等于字符串$z$与符号$a$的连接，那么$x$与$y$的连接等于$x$与$z$的连接与字符$a$的连接

字符串的长度$|w|$：字符串中的符号所占的个数

递归地定义字符串长度：

$|w|=\left\{ \begin{aligned} 0&&w=\varepsilon\\ |x|+1&\quad&w=xa\\ \end{aligned} \right.$

其中，$a\in\Sigma$、$x$是$\Sigma$中的符号组成的字符串。

含义：

• 空串为0
• 如果字符串$w$等于字符串$x$与符号$a$的连接，那么$w$长度等于$x$的长度加一

字符串$x$的$n$次幂：将字符串重复n次

递归地定义字符串的幂：

$x^n=\left\{ \begin{aligned} \varepsilon&&n=0\\ x^{n-1}x&\quad&n>0\\ \end{aligned} \right.$

其中，$n\in\mathbb{N}_+$、$x$是$\Sigma$中的符号组成的字符串。

含义：

• 字符串的0次幂等于空串
• 字符串的$n>0$次幂等于这个字符串的$n-1$次幂与它自身的连接。

字符串集合$A$和$B$的连接：将两集合中的字符串两两连接

$AB=\{w|w=xy\wedge x\in A\wedge y\in B\}$

注：由于字符串的连接不满足交换律，字符串集合的连接也不满足交换律。

字符串集合$A$的$n$次幂：将集合与自身重复连接$n$次

递归地定义字符串集合的幂：

$A^n=\left\{ \begin{aligned} \{\varepsilon\}&&n=0\\ A^{n-1}A&\quad&n>0\\ \end{aligned} \right.$

含义：

• 字符串集合的0次幂等于只有一个空串的集合
• 字符串集合的$n>0$次幂等于这个字符串集合的$n-1$次幂与它自身的连接。

性质

若$\Sigma$为字母表，则$\Sigma^n$为$\Sigma$上长度为$n$的字符串集合。

集合的克林闭包

集合$\Sigma$的克林闭包$\Sigma^*$定义为：

$\Sigma^*=\bigcup_{i=0}^{\infty}\Sigma^i$

克林闭包可以用于定义字母表的克林闭包和字符串集合的克林闭包，因为字母表和字符串集合都是集合。

字母表$\Sigma$上的语言$L$

$L\subseteq\Sigma^*$

注：关于语言，唯一重要的约束就是字母表必须是有穷的。

性质

$\emptyset$和$\{\varepsilon\}$都是任意字母表上的语言。

集合的正闭包

字母表$\Sigma$的正闭包$\Sigma^+$定义为：

$\Sigma^+=\bigcup_{i=1}^{\infty}\Sigma^i$

正闭包可以用于定义字母表的正闭包和字符串集合的正闭包，因为字母表和字符串集合都是集合。

性质

• 字母表的克林闭包等于其正闭包与由一个空字符串组成集合的并集。
• 字符串集合的克林闭包等于其正闭包与由一个空字符串组成集合的并集。

$\Sigma^*=\Sigma^+\cup\{\varepsilon\}$

Next