上下文无关语言的泵引理

定理33：如果语言$L$是CFL，那么存在正整数$N$，对$\forall z \in L$，只要$\vert z \vert \geq N$，就可以将$z$分为五部分$z=uvwxy$满足

• $vx \not= \epsilon$（或$\vert vx \vert \gt 0$）
• $\vert vwx \vert \leq N$
• $\forall i \geq 0,wv^iwx^iy \in L$

证明：

1. 设CNF格式CFG $G$中变元数$\vert V \vert = m$，令$N = 2^m$，若有$z \in L(G)$，且$\vert z \vert \geq N$
2. 则$z$的派生树内节点是二叉树，最长路径长度至少$m+1$，节点至少$m+2$
3. 该路径下由上之上$m+1$个节点中，必有两个$T_2$和$T_1$标记了相同的变元$A$
4. 若标记$T_2$产物为$w$，且是$T_1$的子树，$T_1$的产物可记为$vwx$，则有$A \underset{}{\stackrel{\ast}{\Rightarrow}} vAx$和$A \underset{}{\stackrel{\ast}{\Rightarrow}} w$
5. 那么$\forall i \geq 0, A \underset{}{\stackrel{\ast}{\Rightarrow}} v^iwx^i$。不妨设$z=wvwxy$，则$S \underset{}{\stackrel{\ast}{\Rightarrow}} uAy \underset{}{\stackrel{\ast}{\Rightarrow}} uv^iwx^iy$
6. $T_1$路径长不超过$m+1$，那么$T_1$产物长度不超过$2^m$，所以$\vert vwx \vert \leq 2^m$
7. $T_2$必在$T_1$的左/右儿子中，所以$v$和$x$不可能同时为空，即$vx \not= \epsilon$
   
   阅读全文 »

下推自动机

一个下推自动机和一个$\epsilon$-NFA类似，拥有一个无限长的输入带，一个有穷状态控制器，一个读头。同时具有$\epsilon$-NFA的特性：

• 有限状态
• 非确定
• $\epsilon$转移
  与之不同的是，下推自动机增加一个符号栈，符号栈有一个读写头，读写的时候后进先出，只用栈顶，栈长度无限。
• $pop$：仅仅弹出栈顶一个符号
• $push$：可压入一个符号串

读头从输入带上一次读入一个字符，并向右移动一个单位长度，控制符号栈读头弹出一个符号。有穷控制器根据读入的字符，弹出的栈顶符号以及当前的状态，修改当前状态，并向符号栈压入一个新串。

下推自动机能识别的语言比有穷自动机更多

阅读全文 »

上下文无关文法

自然语言文法

一个英语语法的例子：

$$\begin{aligned} \langle sentense \rangle &\to \langle noun-phrase \rangle \langle verb-phrase \rangle \\ \langle noun-phrase \rangle &\to \langle article \rangle \langle noun \rangle | \langle article \rangle \langle adjective \rangle \langle noun \rangle \\ \langle verb-phrase \rangle &\to \langle verb \rangle | \langle verb \rangle \langle none-phrase \rangle \\ \langle article \rangle &\to \boldsymbol{a} \vert \boldsymbol{the} \\ \langle noun \rangle &\to \boldsymbol{boy} \vert\boldsymbol{girl} \vert \boldsymbol{cat} \\ \langle verb \rangle &\to \boldsymbol{sees} \vert \boldsymbol{likes} \\ \dots \\ \end{aligned}$$

根据语法结构，可以从$ \langle sentense \rangle$推出一个句子：

$$\begin{aligned} \langle sentense \rangle &\Rightarrow \langle noun-phrase \rangle \langle verb-phrase \rangle \\ &\Rightarrow \langle article \rangle \langle noun \rangle \langle verb-phrase \rangle \\ &\Rightarrow \langle article \rangle \langle noun \rangle \langle verb \rangle \langle noun-phrase \rangle \\ &\Rightarrow \langle article \rangle \langle noun \rangle \langle verb \rangle \langle article \rangle \langle adjective \rangle \langle noun \rangle \\ &\Rightarrow \boldsymbol{the} \langle noun \rangle \langle verb \rangle \langle article \rangle \langle adjective \rangle \langle noun \rangle \\ &\Rightarrow \boldsymbol{the \ girl} \langle verb \rangle \langle article \rangle \langle adjective \rangle \langle noun \rangle \\ &\Rightarrow \dots \\ &\Rightarrow \boldsymbol{the \ girl \ sees \ a \ blue \ cat} \end{aligned}$$

很显然，这个句子是符合$\langle sentense \rangle$的句子结构的。从$ \langle sentense \rangle$到句子这一过程，使用的过程就是文法。

正则表达式

• $\to$正则表达式
  • 正则表达式的递归定义
  • 正则表达式实例
• 自动机和正则表达式
• 正则表达式的代数定理

• 有穷自动机
  • 通过机器装置描述正则语言
  • 用计算机编写相应算法，用于实现

• 正则表达式

  • 通过表达式描述正则语言，代数表示方法，使用方便
  • 应用广泛
    • grep工具（Global Regular Expression and Print)
    • Emacs/Vim文本编辑器
    • lex/flex词法分析器
    • 各种程序设计语言Python/Perl/Haskell…

  本文正则表达式并非POSIX正则表达式，只是一种形式化的表示

  阅读全文 »

课程介绍

计算理论

• 对计算本质的探索
• 计算：非纯粹的算数，是一种以计算为有效的方式，获取答案的过程
• 计算理论促进了计算机的发展，并随着计算机的诞生将重心转移到计算科学

核心问题：计算机的基本能力和限制是什么？
包含了两个方面：

• 可计算性理论：有哪些问题可以通过计算来解决？计算这种能力是否有边界？如果不是，为什么不是？对于严谨的机械而有效的过程的研究，我们需要严格定义的概念（算法）去描述它，需要严谨的模型（自动机理论）去分析它。
• 计算复杂性理论：利用计算去解决可计算的问题，需要消耗多少资源

自动机理论：研究抽象机器及其所能解决的问题的理论，主要包括：

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

自动机是研究语言的模型，语言则是具体的实例。自动机以语言为处理对象，语言以自动机为形式定义，两者密不可分。

形式语言：经数学定义的语言
语言：字符，单词，句子，语法

课程内容：

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