简介及基础知识

主要内容

• 正则语言
  • 有穷自动机
  • 正则表达式
  • 正则语言的性质
• 上下文无关语言
  • 上下文无关文法
  • 下推自动机
  • 上下文无关语言的性质
• 计算导论
  • 图灵机及其扩展
  • 不可判定性

计算机问题求解思路：问题\(\to\)形式化描述\(\to\)自动化（计算机化）

图灵机

图灵机是一种假想的设备，它根据规则表操纵纸袋上的符号，并进行状态之间的转移

最具变革意义：第一次在纯数学的符号逻辑和实体世界之间建立了联系

基础知识

形式化描述

用基于数学的方法以形式化规约语言对问题、模型等进行精确描述，是科学研究的基础。

形式化证明

1. 演绎法
   • 从一般性原理出发，依据已被确认的事实或者公认的逻辑规则，推导出某个特殊情况下的结论
2. 归纳法
   • 由某类事物的部分对象具有某些特征，推导出该类事物的全部对象都具有这些特征的过程，是由个别事实概括出一般结论的过程
3. 反证法
   • 假设某命题不成立（即在原命题的题设下，结论不成立），然后推理出明显矛盾的结果，从而判定假设不成立，原命题得证

自动机理论

研究抽象机器及其所能解决问题的理论

• 有限状态机
• 图灵机
• 文法，下推自动机

形式语言

经数学定义的语言

	自然语言		形式语言
	English	中文	化学分子式	C语言
字符	A,a,B,b...	天，地...	A-Z,a-z,0-9	A-Z,a-z,0-9
单词	water	水	H2O	char
句子	How' re you?	你好！	2H2+O2=2H2O	char ch='a';
语法	Grammar	语法规则	精确定义的规则

字符串基本概念

字母表：符号（字符）的非空有穷集

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

空串:记为\(\epsilon\)，有0个字符的串

字符串的长度：字符串中符号所占位置的个数，记为|∙|

字符串x和y的连接：将首尾相接得到新字符串的运算, 记为\(x\cdot y\) 或\(xy\)

字符串x的n次幂(n≥0)：递归定义为

\[x^n=\begin{cases}\epsilon&n=0\\x^{n-1}x&n>0\end{cases}\]

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

如果\(\Sigma=\{0,1\}\)，有\(\Sigma^0=\{\epsilon\}\)，

\(\Sigma^1=\{0,1\}\)

\(\Sigma^2=\{00，01，10，11\}\)

\(\Sigma^3=\{000，001，010，011，100,101,110,111\}\)...

克林闭包

\[{{\Sigma}}^*=\bigcup_{i=0}^{\infty} \Sigma_i\]

正闭包

\[{{\Sigma}}^*=\bigcup_{i=1}^{\infty} \Sigma_i\]

集合的克林闭包可能与正闭包相等，如：\(\Phi，\{\epsilon\}\)
\(\phi^*=\phi\cup \phi^+\quad \{\epsilon\}^*=\{\epsilon\}\cup\{\epsilon\}=\{\epsilon\}\)

语言

若\(\Sigma\)为字母表且\(\forall L \subseteq {\Sigma}^*\), 则L称为字母表\(\Sigma\)上的语言

关于语言唯一重要的约束就是所有字母表都是有穷的

典型问题

判定给定的字符串w是否属于某个具体的语言L？（\(w\in L?\)）