自动人形会梦见 NP 完全问题吗？(笔记)

Posted on 繁/简： set

计算理论 (Theory of Computation) 当之无愧是计算机科学王冠上的明珠；考虑到我贫瘠的智商，以后估计不会朝 TCS 方向来走；但对这些优雅的理论有一个最基本的了解应当是 CS 学生的素养。

讽刺的是，你坑近二十年前就没有开设这门课了 [1]，只得留待交换来上。老师是印度人，口音很重，我听完整节课才明白他口中的「GEO」其实是「zero」；但课还是讲得十分清楚，颇有 Ravi 之风。


  This article is a self-administered course note.

  It will NOT cover any exam or assignment related content.


Preliminaries

关于 formal proof 的一些 recap，一些自动机理论概念的 notations 与定义。

字母表 (alphabet) \(\Sigma\), 符号/字符 (symbol), 字符串 (string) 与语言 (language) \(L\subseteq \Sigma^{*}\)。

关于 strings/languages 的可数性质：

  • Number of strings over any non-empty alphabet is countable. e.g., length then lexicographic order.
  • Number of languages over any non-empty alphabet is uncountable. Remember that language is just a subset of the set of all strings.


DFA, NFA and RegEx

关于 \(\epsilon\)-transition。不输入任何 symbol 的转移。\(\epsilon\) closure \(\text{Eclose}(q)\)。

regular language is a set of strings, regular expression \(M\) is a representation of regular language \(L(M)\).

DFA & NFA: Equivalence

NFAs and DFAs are equivalent in terms of the languages they can recognize, even though DFAs may require more states (potentially exponentially more) than NFAs.

首先 DFA 一定是 NFA。

对于给定的 NFA \(A=(Q,\Sigma, \delta,q_0,F)\) 构建等价的 DFA \(A_D=(Q_D,\Sigma,\delta_D,\{q_0\},F_D)\)。定义 \(Q_D=\{S|S\subseteq Q\}\) (因此 \(|Q_D|\) 是 \(O(2^{|Q|})\) 级别的)，\(F_D=\{S|S\subseteq Q \text{ and } S\cap F\neq \emptyset\}\)，\(\delta_D(S,a)=\bigcup_{q\in S}\delta(q,a)\)。

Claim. If for all string \(w\), \(\hat\delta_D(\{q_0\},w)=\hat\delta(q_0,w)\), then \(\hat\delta_D(\{q_0\},wa)=\hat\delta(q_0,wa)\) also holds.

Base case. \(w=\epsilon\), \(\hat\delta_D(\{q_0\},\epsilon)=\{q_0\}=\hat\delta(q_0,\epsilon)\) holds.

Induction case. \[ \begin{aligned} \hat\delta_D(\{q_0\},wa)&=\delta_D(\hat\delta_D(\{q_0\},w),a) \\ &=\bigcup_{q\in\hat\delta_D(\{q_0\},w)}\delta(q,a) \\ &=\bigcup_{q\in \hat\delta(q_0,w)} \delta(q,a) \\ &=\hat\delta(q_0,wa) \end{aligned} \] 因此我们构建出的 DFA \(A_D\) 能够接受字符串 \(w\)，当且仅当 NFA \(A\) 接受字符串 \(w\)。

DFA to RegEx

本质 DP。对于给定的 DFA \(A=(Q,\Sigma,\delta,q_{start}, F)\)，不妨定义 \(Q=\{1,2,...,n\}\) 且 \(q_{start}=1\)。定义 \(R_{i,j}^k\) 为从 \(i\) 到 \(j\)，只能经过标号 \(\leq k\) 状态的路径所对应的 RegEx。

Base case. 定义 \(R_{i,j}^0\)

  • If \(i\neq j\). \(R_{i,j}^0=a_1+a_2+...+a_m\) for all \(\delta(i,a_r)=j\).
  • If \(i=j\). \(R_{i,j}^0=\epsilon+a_1+a_2+...+a_m\) for all \(\delta(i,a_r)=i\).

Induction case. \(R_{i,j}^{k+1}=R_{i,j}^k+R_{i,k+1}^k(R_{k+1,k+1}^k)^{*}R_{k+1,j}^k\)

那么该 DFA 所对应的 regular expression 为 \(L(A)=\sum_{j\in F} R_{1,j}^n\)

RegEx to \(\epsilon\)-NFA

对于给定的 RegEx，构建 start state 与 final state 唯一的 \(\epsilon\)-NFA。

Base case.

  • \(\emptyset\). \(A=(\{q_0,q_f\}, \Sigma,\delta,q_0,\{q_f\})\) where \(\delta\) is an empty transition.
  • \(\epsilon\). \(A=(\{q_0,q_f\}, \Sigma,\delta,q_0,\{q_f\})\) where \(\delta(q_0,\epsilon)=q_f\).
  • \(a\). \(A=(\{q_0,q_f\}, \Sigma,\delta,q_0,\{q_f\})\) where \(\delta(q_0,a)=q_f\).

Induction case. 对于 \(r_1\) 对应的 \(A_1=(Q_1,\Sigma,q_0^1,\delta_1,F_1)\) 与 \(r_2\) 对应的 \(A_2=(Q_2,\Sigma,q_0^2,\delta_2,F_2)\)，分别为 \(r_1+r_2\), \(r_1\cdot r_2\), \(r_1^*\) 构造新的 \(\epsilon\)-NFA \(A=(\{q_0,q_f\}\cup Q_1\cup Q_2,\Sigma,\delta,q_0,\{q_f\})\)。

  • \(r_1+r_2\). 添加 \(\delta(q_0,\epsilon)=\{q_0^1,q_0^2\}\), \(\epsilon(q_f^1,\epsilon)=\{q_f\}\) for all \(q_f^1\in F_1\), \(\delta(q_f^2,\epsilon)=\{q_f\}\) for all \(q_f^2\in F_2\)。
  • \(r_1\cdot r_2\). 添加 \(\delta(q_0,\epsilon)=\{q_0^1\}\), \(\delta(q_f^1,\epsilon)=\{q_0^2\}\) for all \(q_f^1\in F_1\), \(\delta(q_f^2,\epsilon)=\{q_f\}\) for all \(q_f^2\in F_2\)。
  • \(r_1^*\). 添加 \(\delta(q_0,\epsilon)=\{q_0^1, q_f\}\), \(\delta(q_f^1,\epsilon)=\{q_0^1,q_f\}\) for all \(q_f^1\in F_1\).


Minimization of DFA

Equivalence Classes

给定 regular language \(L\)。

  • \(u\equiv_L w\) iff for all \(x\), \(ux\in L\) iff \(wx\in L\).
  • \(\equiv_L\) is an equivalence relation - it is reflexive, symmetric, and transitive.
  • 通过 equivalence classes \(\text{equiv}(w)\) 构造 minimal DFA \((Q, \Sigma, \delta,q_0,F)\)
    • \(Q=\{\text{equiv}(w):w\in \Sigma^*\}\)
    • \(q_0=\text{equiv}(\epsilon)\)
    • \(F=\{\text{equiv}(w):w\in L\}\)
    • \(\delta(\text{equiv}(w), a)=\text{equiv}(wa)\)

该方法对给定的 regular language \(L\) 构造一个 unique 且 minimal 的 DFA \(A\) from scratch。

Distinguishable Pairs

给定 DFA \(A=(Q,\Sigma,\delta,q_0,F)\)。通过合并 non-distinguishable pairs 的方式找到其对应的 minimal DFA。其实，本质上就是找到一个将 \(\equiv_A\) 划分为 finer equivalence classes \(\equiv_L\) 的过程。

  • Base case. \(\epsilon\) of length \(0\) distinguishes the accepting and non-accepting states.
  • Induction case. suppose the algorithm finds all pairs of states distinguished using strings of length at most \(k\), then, consider states \((p,q)\) distinguished using string \(w=ax\) of length \(k+1\).
  • If the pair \((\delta(p,a),\delta(q,a))\) are distinguishable, then \((p,q)\) are distinguishable.

画一张 \(|Q|\times |Q|\) 的表格标记所有的 distinguishable pairs，并按照上述的长度归纳法把它们都找出来；剩下的 pairs 即是 non-distinguishable pairs，把它们合并即可。


Properties of Regular Languages

Pumping Lemma

Let \(L\) be a regular language. There exists a constant \(n\) such that for every string in \(L\) satisfying \(|w|\geq n\), we can break \(w\) into three strings \(w=xyz\), such that,

  • \(y\neq \epsilon\)
  • \(|xy|\leq n\)
  • For all \(k\geq 0\), the string \(xy^kz\) is also in \(L\)

这里的 \(n\) 实际上就是 \(L\) 对应的 DFA 中 states 的数目，即 \(n=|Q|\)。只要 \(L\) 中存在长度 \(\geq n\) 的字符串，说明 DFA 中一定存在环 (鸽巢原理)；该环对应的就是 \(y\)。

Pumping lemma 一般用来证否，即，通过找到某个长度 \(\geq n\) 的字符串 \(xyz\)，其扩增过后的 \(xy^kz\notin L\)，进而说明 \(L\) 并非 regular language。

Closure Properties

  • 之前提到的，若 \(L_1,L_2\) 是 regular language，so are \(L_1\cup L_2,L_1\cdot L_2,L_1^*\)
  • so are \(L_1\cap L_2,L_1-L_2,\overline{L}=\Sigma^*-L, L^R\)
  • \(h\) is a homomorphism, if \(L\) is regular, so is \(h(L)\)

Homomorphism

\(\Sigma\) and \(\Gamma\) are two alphabets. Define homomorphism \(h:\Sigma\to\Gamma^*\) such that,

  • \(h(\epsilon)=\epsilon\)
  • (extend to string) \(h(aw)=h(a)\cdot h(w)\)

If \(L\) is regular then \(h(L)=\{h(w)|w\in L\}\) is also regular.

新的证明模式：若 \(M\) 是 \(L\) 的 RegEx，定义 \(R(M)\) 满足以下条件 (RegEx 的性质) 并说明 \(R(M)\) 所对应的是 \(h(L(M))\)。即，通过说明 \(h(L(M))\) 存在 RegEx 的形式证明 \(h(L(M))\) 本身是 regular language。

  • \(R(\emptyset)=\emptyset\)
  • \(R(\epsilon)=\epsilon\)
  • \(R(a)=h(a)\) for \(a\in \Sigma\)
  • \(R(M+N)=R(M)+R(N)\)
  • \(R(M\cdot N)=R(M)\cdot R(N)\)
  • \(R(M^*)=(R(M))^*\)

Base case. \(L(R(\emptyset))=h(L(\emptyset))=\emptyset, L(R(\epsilon))=h(L(\epsilon))=\epsilon, L(R(a))=h(L(a))=h(a)\).

Induction case. 完整的证明应当包括 \(M+N,M\cdot N,M^*\)。这里以证明 \(M+N\) 为例：若 \(L(R(M))=h(L(M))\) 且 \(L(R(N))=h(L(N))\)，求证 \(L(R(M+N))=h(L(M+N))\)。 \[ \begin{aligned} L(R(M+N))&=L(R(M)+R(N)) \ \ \text{by definition} \\ &= L(R(M)) + L(R(N)) \\ &= h(L(M))+h(L(N)) \\ &= h(L(M+N)) \end{aligned} \] 注意把握好 regular language 与 RegEx 间的关系。这里就 implicitly 应用了 \(L(M+N)=L(M)+L(N)\)。


Context Free Grammars (CFG)

Context-Free Grammars (CFG) 是一种语法，通过 derivation 过程生成对应的 language。

  • CFG \(G=(V,T,P,S)\).
  • \(L(G)=\{w\in T^{*}|S\Rightarrow^*_G w \}\). 即，从 start symbol \(S\) 开始，能够 derive 出字符串 \(w\in\) terminals \(T^*\).
  • If \(S\Rightarrow^*_G \alpha\), \(\alpha\) is called a sentential form (without any non-terminals).

Right-Linear Grammars

A CFG is right-linear if all the productions in it are of the form,

  • \(A\to wB\) for \(B\in V\) and \(w\in T^*\), or
  • \(A\to w\), for \(w\in T^*\)

右线性文法的两个重要性质：

  • Every regular language can be generated by some right-linear grammar.
  • Language generated by a right-linear grammar is regular.

证明 \(1\)：若 regular language \(L\) 被 DFA \(A=(Q,\Sigma,\delta,q_0,F)\) 识别，根据 \(A\) 一定能构造出 right-linear CFG \(G\).

  • \(G=(Q,\Sigma,P,q_0)\)
  • If \(\delta(q,a)=p\), then there is a production in \(P\) of the form \(q\to ap\).
  • If \(q\in F\), then \(q\to \epsilon\).

通过一个简单的 induction by length 可以得到 \(\hat\delta(q_0,w)\in F \iff q_0\Rightarrow^*_G w\).

证明 \(2\)：给定 right-linear CFG \(G=(V,\Sigma,P,S)\)，证明 \(G\) derive 出的 language \(L(G)\) 一定能被某 NFA \(A\) 识别。

  • \(A=(V,\Sigma,\delta,S,F)\)
  • If \((A\to aB)\in P\), then \(B\in \delta(A,a)\).
  • \(F=\{A|(A\to\epsilon)\in P\}\).

相似的，可证得 \(A\Rightarrow_G^* wB \iff B\in\hat\delta(A,w)\)，那么有 \(S\Rightarrow_G^* w\iff \hat\delta(S,w)\cap F\neq \emptyset\).

Ambiguous Grammars

在模糊文法中，同一个字符串可能有多种不同的 derivations。我们可以通过定义 operator precedence 等规则来消除文法中的 ambiguity。但也存在 inherently ambiguous languages，它对应的文法总是 ambiguous 的。


Push Down Automata (PDA)

下推自动机。带一个容量无限栈 (作为 memory) 的 \(\epsilon\)-NFA。

  • \(P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)\)
  • \(\Sigma\): Alphabet set, \(\Gamma\): Stack alphabet set. \(Z_0\): the only initial symbol on the stack.
  • \((p,\gamma)\in \delta(q,a,X)\): in state \(p\), reading \(a\), with top of stack being \(X\), the machine's new state is \(p\), \(X\) is popped and \(\gamma\) is pushed. (if \(\gamma=RS\), \(S\) is pushed first, then \(R\))
  • Instantaneous description \((q,w,a)\) denotes current state is \(q\), input left to read is \(w\), and \(\alpha\) being the top of the stack. \((q,aw,X\alpha)\vdash (p, w,\beta\alpha)\) if \((p, \beta)\in \delta(q, a,X)\). Extend \(\vdash\) to \(\vdash^*\).

Equivalent PDAs

PDA 按照不同的 language acceptance 方式分为两种。

  • By final state: \(\{w|(q_0,w,Z_0)\vdash^*(q_f,\epsilon,\alpha), \text{ for some }q_f\in F\}\).
  • By empty stack: \(\{w|(q_0,w,Z_0)\vdash^*(q,\epsilon,\epsilon)\text{ for some }q\in Q\}\).

其实这两种 PDA 是等价的。

From empty-set to final-state PDA - initially put a special symbol onto the stack. (give control to empty-set PDA), if ever see the top of stack as that symbol (seize control), then go to final state.

From final-state to empty-set PDA - place a transition from final state to a special state which empties the stack.

  • for all \(p\in F\) and \(Z\in \Gamma\cup\{X_0\}\), \(\delta_E(p,\epsilon,Z)\) contains \((p_f,\epsilon)\)
  • (pop until empty) for all \(Z\in \Gamma\cup \{X_0\}\), \(\delta_E(p_f,\epsilon,Z)\) contains \((p_f,\epsilon)\)

Equivalence of CFGs and PDAs

CFG 和 PDA 本质等价。

First show how to accept a CFG with an empty-stack PDA (easy).

Given \(G=(V,T,P,S)\), construct \(PDA=(\{q_0\},\Sigma,\Gamma,\delta,q_0,S,F)\), where

  • \(\Sigma=T\)
  • \(\Gamma=V\cup T\)
  • For all \(a\in \Sigma\), \(\delta(q_0,a,a)=\{(q_0,\epsilon)\}\) [terminal alphabet is eliminated directly]
  • For all \(A\in V\), \(\delta(q_0,\epsilon,A)=\{(q_0,\gamma):A\to \gamma \text{ in } P\}\) [non-terminal alphabet is substituted]

Next show each language accepted by an empty-set PDA can be accepted by a CFG (hard).

Given \(PDA=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)\), construct grammar \(G=(V, \Sigma,R,S)\), where

  • \(V=\{S\}\cup\{[qZp]:p,q\in Q,Z\in \Gamma\}\)
  • For each \(p\in Q\), \(S\to [q_0Z_0p]\) [in state \(q\), with top of the stack being \(Z_0\), going to state \(p\)]
  • If \(\delta(q,a,X)\) contains \((r, Y_1...Y_k)\), \([qXr_k]\to a[rY_1r_1][r_1Y_2r_2]...[r_{k-1}Y_kr_k]\), for all \(r_1,r_2,...,r_k\in Q\). [produce \(a\), but need to get rid of \(Y_1...Y_k\) one by one. The actual discarding path is permutated.]
  • Notice if \(k=0\), \([qXr]\to a\)

According to the above definition, \([qXr]\) generates \(w\) iff \((q,w,X)\vdash^*(r, \epsilon,\epsilon)\) (stack being emptied), if inducted on number of steps of PDA or derivation in the CFG.

Deterministic PDA (DPDA)

与原始定义的 NPDA 不同，DPDA,

  • there is at most one element in \(\delta(q,a,Z)\)
  • if \(\delta(q,\epsilon,X)\) is non-empty, for all \(a\in\Sigma\), \(\delta(q,a,X)\) is empty.

三个性质：

  • 不同于等价的 DFA/NFA，存在能被 NPDA 接受但无法被任何 DPDA 接受的语言。
  • (退化为 DFA/NFA) Every regular language can be accepted by a final-state DPDA.
  • Any language accepted by an empty-stack DPDA has prefix property: For every \(x,y\) in the language, \(x\) is not a prefix of \(y\). e.g., language \(\{a.aa\}\) is not accepted by any DPDA.


Reference

  This article is a self-administered course note.

  References in the article are from corresponding course materials if not specified.

Course info: CS3231. Professor: Sanjay Jain.

Course textbook: Introduction to Automata Theory, Languages and Computation (3rd Edition), Hopcraft, Motwani & Ullman, (2014), Pearson

Course website: https://www.comp.nus.edu.sg/~sanjay/cs3231.html

[1] 引自杨老师，摘录如下：「据考证，本科生课程 CSIS0293/COMP3293 Introduction to Theory of Computation 最后一次开设是在 Autumn 2005，研究生课程 CSIS9601/COMP9601 Theory of Computation and Algorithm Design 最后一次开设是在 Autumn 2016。」

-----------------------------------そして、次の曲が始まるのです。-----------------------------------