計算理論 (Theory of Computation) 當之無愧是計算機科學王冠上的明珠；考慮到我貧瘠的智商，以后估計不會朝 TCS 方向來走；但對這些優雅的理論有一個最基本的了解應當是 CS 學生的素養。

諷刺的是，你坑近二十年前就沒有開設這門課了 [1]，只得留待交換來上。老師是印度人，口音很重，我聽完整節課才明白他口中的「GEO」其實是「zero」。

{% note warning %}

? This article is a self-administered course note.

? It will NOT cover any exam or assignment related content.

{% endnote %}

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.

因此我們構建出的 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，把它們合并即可。

Parallel Simulation of 2-DFAs

Given \(A=(Q,\Sigma,\delta,q_0,F)\) and \(A'=(Q’, \Sigma,\delta',q_0',F')\).

Construct \(A''=(Q\times Q',\Sigma,\delta'',(q_0,q_0'),F'')\), where \(\delta''((q,q'),a)=(\delta(q,a),\delta'(q',a))\). DFA \(A''\) simulates the two DFAs \(A\) and \(A'\) in parallel.

• If we take \(F''=F\times F'\), then the new DFA \(A''\) accepts \(L(A)\cap L(A')\).
• If we take \(F''=F\times Q'\cup Q\times F'\), then the new DFA \(A''\) accepts \(L(A)\cup L(A')\).
• Appropriate choice of \(F''\) results in other boolean combination of languages accepted by \(A\) and \(A'\).

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。

Properties

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)\)

Calculation Properties.

• \(M+N=N+M\), \(L(M+N)=LM+LN\)
• \(L+L=L\), \((L^*)^*=L^*\), \(L^+=LL^*=L^*L\), \(L^*=\epsilon+L^+\)
• \((L+M)^*=(L^*M^*)^*\)

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))\)。

注意把握好 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.

Properties of CFGs

Useful Symbols

三個定義。

• Symbol \(A\) is useful if it appears as \(S\Rightarrow ^*_G \alpha A\beta \Rightarrow^*_G w\) for some \(w\in T^*\).
• Symbol \(A\) is generating if \(A\Rightarrow_G^* w\), for some \(w\in T^*\).
• Symbol \(A\) is reachable if \(S\Rightarrow^*_G \alpha A\beta\), for some \(\alpha,\beta \in (V\cup T)^*\).

A symbol is useful only if it is reachable and generating (vice versa need not be the case).

因此，給定一個 \(G=(V,T,P,S)\) which generates at least one string，通過以下兩步可以創造一個等價的 (生成的 language 與 \(G\) 相同) CFG，且它不包含任何 useless symbols。

• eliminate all symbols (and productions involving these symbols) that are non-generating.
• eliminate all symbols (and productions involving these symbols) that are non-reachable.

Chomsky Normal Form

Chomsky Normal Form: All productions are of the form \(A\to BC\) or \(A\to a\) (where \(a\in T\) and \(A,B,C\in V\)).

All CFGs can be converted to Chomsky Normal Form.

• Eliminate \(\epsilon\) productions.
• Eliminate unit productions.
• Convert all productions into the following forms:
  • productions of length \(2\): \(A\to BC\) where \(B,C\) are non-terminals.
  • productions of length \(1\): \(A\to a\) where \(a\) is a terminal.

首先來看第一步：消除所有 \(\epsilon\) productions。重復以下過程，直到 \(G\) 中不存在任何 \(\epsilon\) production：

• Identify nullable state. e.g., If \(A\to\epsilon\), then \(A\) is nullable.
• Remove \(\epsilon\) production associated to the nullable state. e.g., remove \(A\to \epsilon\).
• For each production \(B\to\alpha\), replace it with all possible \(B\to\alpha'\) resulted in possibly deleting some of the nullable non-terminals. e.g., \(S\to ASA|aB|a\) is replaced by \(S\to ASA|SA|AS|S|aB|a\).

接下來是第二步：消除所有 unit productions。重復以下過程，直到 \(G\) 中不存在任何 unit production：

• Identify non-terminal pair. e.g., If \(A\to B\), then \((A,B)\) is a pair.
• Remove unit production associated to the pair. e.g., remove \(A\to B\).
• For each non-unit productions of the form \(B\to \gamma\), add production \(A\to \gamma\).

經以上兩步處理，\(G\) 中所有的 productions \(A\to \alpha\) 都表現為以下兩個形式。

• \(|\alpha|=1\)，此時 \(\alpha\) 一定是 terminal。
• \(|\alpha|=|\alpha_1\alpha_2...\alpha_n|=n\geq 2\)，\(\alpha_i\) 既可以是 terminal 又可以是 non-terminal。

此時我們應用第三步，將第二種形式再進一步化成 \(A\to BC\) 且 \(B,C\) 均為 non-terminal 的形式：Given production \(A\to X_1X_2...X_k\) is changed to the following set of productions with new non-terminals \(B_i,Z_i\):

• \(A\to Z_1B_2,\)
• \(B_2\to Z_2B_3,...,\)
• \(B_{k-1}\to Z_{k-1}B_k,\) (two non-terminals, the second form)
• \(Z_i\to X_i\) if \(X_i\in T\) (one terminal, the first form)
• \(Z_i=T_i\) if \(X_i\in V\)

喬姆斯基范式下的 CFG \(G\) 的優美性質：其 parse tree 是一顆二叉樹！若該二叉樹的最大深度為 \(s\)，\(G\) 所生成語言的 size 是 \(O(2^{s-1})\) 級別的。

Pumping Lemma for CFL

Let \(L\) be a CFL (Context Free Language, languages generated by CFG). Then there exists a constant \(n\) such that, if \(z\) is any string in \(L\) such that \(|z|\geq n\), then we can write \(z=uvwxy\) such that,

• \(|vwx|\leq n\)
• \(vx\neq \epsilon\)
• For all \(i\geq 0\), \(uv^iwx^iy\in L\).

Proof (所有 pumping lemma 證明的重點都在于重復). Given Chomsky Normal Form grammar \(G=(V,T,P,S)\) for \(L-\{\epsilon\}\). Let \(m=|V|\). Let \(n=2^m\).

Suppose a string \(z\in L\) of length at least \(n=2^m\) is given. Consider the parse tree for \(z\), it must have a path from the root to a leaf of length at least \(m+1\) (完全二叉樹深度最小，但仍有 \(m+1\)).

In this path, among the last \(m+1\) non-terminals, there must be two non-terminals which are the same (by pigeonhole principle).

Then, \(z=uvwxy\), where \(S\Rightarrow ^*_G uAy \Rightarrow _G^* uvAxy \Rightarrow uvwxy\).

• Thus, we have \(A\Rightarrow ^*_G vAx,A\Rightarrow_G^* w\)
• Thus, \(A\Rightarrow_G^*v^iAx^i\Rightarrow_G^* v^iwx^i\)
• Thus, \(S\Rightarrow_G^* uAy\Rightarrow_G^*uv^iwx^iy\) for all \(i\) [condition 3]

Since \(A\) is a subtree of \(S\), the length of \(vwx\) is at most \(2^m=n\) [condition 1] Since \(G\) is in Chomsky Normal Form, it does not have any unit productions or \(\epsilon\) productions. Therefore, as \(A\Rightarrow_G^* vAx\), \(vx\neq \epsilon\) [condition 2]

Closure Properties

Substitution (類似 homomorphism).

Consider mapping each terminal \(a\) to a CFL \(L_a\), \(s(a)=L_a\). For a string \(w\), define \(s(w)\) as follows:

• \(s(\epsilon)=\{\epsilon\}\)
• \(s(wa)=s(w)\times s(a)\), for \(a\in\Sigma, w\in \Sigma^*\)

If \(L\) is CFL over \(\Sigma\) and \(s\) is a substitution on \(\Sigma\) such that \(s(a)=L_a\) is CFL for each \(a\in\Sigma\). Then, \(\cup_{w\in L}s(w)\) is a CFL (證明很簡單，把原 \(P\) 中所有的 \(A\to a\) 替換成 \(A\to S_a\)：\(S_a\) 是 \(L_a\) 對應的 starting state).

Reversal.

If \(L\) is CFL, then \(L^R\) is CFL (將原 \(P\) 中所有的 \(A\to \alpha\) 替換成 \(A\to\alpha^R\))

Union.

If \(L\) is CFL and \(R\) is regular, then \(L\cap R\) is CFL.

證明：parallel simulation of PDA for \(L\) and DFA for \(R\).

• For \(Z\in \Gamma,p\in Q,q\in Q'\), \(\delta''((p,q),\epsilon,Z)=\delta(p,\epsilon,Z)\times \{q\}\)
• For \(a\in\Sigma,Z\in \Gamma,p\in Q,q\in Q'\): \(\delta''((p,q),a,Z)=\delta(p,a,Z)\times \{\delta'(q,a)\}\)

注意一定是 CFL \(\cap\) RL，不能是 CFL \(\cap\) CFL。例如，\(L_1=\{a^nb^nc^m:m,n\geq 1\}\) 與 \(L_2=\{a^mb^nc^n:m,n\geq 1\}\) 均是 CFL (忽略 \(m\)，判斷 \(n=n\))，但 \(L_3=L_1\cap L_2=\{a^nb^nc^n:n\geq 1\}\) 不是 context free 的 (單棧 PDA 只能處理兩個長度相等的符號，三個就不行了)。

Empty.

A CFL is \(\emptyset\) if \(S\) is a useless symbol. Otherwise it is non-empty.

CYK Algorithm

CYK 算法 (Cocke-Younger-Kasami algorithm) 用于 CFL 的 membership testing (判斷某個字串 \(w\) 是否屬于給定的 CFL \(L\))。它是一個 \(O(n^3)\) 的 DP 算法。

將 \(L\) 化為 Chomsky Normal Form。對于 \(w=a_1...a_n\)，定義 \(X_{i,j}\) 為所有能生成 \(a_ia_{i+1}...a_j\) 的 non-terminals。

• Base case. \(X_{i,i}\) is the set of non-terminals which generate \(a_i\).
• Induction step. \(X_{i,j}\) contains all \(A\) such that \(A\to BC\) and \(B\in X_{i,k}, C\in X_{k+1,j}\), for \(i\leq k<j\).

\(w=a_1...a_n\) is in the language iff \(X_{1,n}\) contains \(S\).

Turing Machine: Some Concepts

Turing Machine \(M=(Q,\Sigma,\Gamma,\delta,q_0,B,F)\)

• \(\Sigma\): input alphabet set. \(\Gamma\): tape alphabet. \(\Sigma\subseteq \Gamma\).
• \(\delta: Q\times \Gamma \to Q\times \Gamma\times \{L,R\}\) (state, read \(\to\) new_state, write, move left/right)
• \(B\): blank symbol, \(B\in \Gamma-\Sigma\)
• \(F\): set of final states. \(F\subseteq Q\)

Instantaneous Description. \(x_0x_1,...,x_{n-1}qx_nx_{n+1}...x_m\) (無限長紙帶，讀寫頭對應的狀態)

TM accepts \(x\) iff \(q_0 x \vdash^* \alpha q_f\beta\) (只要在轉移過程中能夠到達 \(q_f\in F\)，紙帶上的字符串 \(x\) 即可視為被對應的圖靈機接受；與 DFA/PDA 不同，不需要 consume \(x\) 中的所有字符)。\(L(M)=\{x|q_0 x \vdash^* \alpha q_f \beta, q_f\in F\}\).

Function computed by Turing Machine.

• Machine halts on input \(x\) iff \(f(x)\) is defined.
• \(f(x)\) 是圖靈機在輸入 \(x\) 上停機后紙帶上的結果。
• This reveals that machine may never halt.

Coding of Turing Machine. Since Turing machines can be represented by finite descriptions (such as code or a set of rules), it is possible to enumerate them in an ordered way.

Church-Turing Thesis. Whatever can be computed by an algorithmic device (in function computation sense, or language acceptance sense), can be done by a Turing Machine.

Semi-Infinite-Tape TM

想象一下把紙帶對折，以最左邊的 cell 為界，紙帶被分為 upper track 與 lower track。顯然，lower track 中的「往右」實際上對應著原紙帶中的「往左」。

Turing machines with semi-infinite tape are equivalent to standard Turing machines.

對 standard TM 的 simulation 如下 (新增 \(U,D\) 標記 upper track, lower/down track)：

Initialization. \(\delta(q_S,(X,B))=((q_0,U),(X,*),S)\): From \(q_S\), read \((X,B)\), goes to state \((q_0,U)\) [\(q_0\) on upper track], write \(X\) on upper track, \(*\) on lower track, do not move.

Simulation. Below \(X,Z\in \Gamma\) and \(m\in\{L,R\}\).

• If \(\delta(q,X)=(q',Y,m)\) [不在分界線上]
  • upper track. \(\delta'((q,U),(X,Z))=((q',U),(Y,Z),m)\) [rewrite \(X\) to \(Y\) if on upper track]
  • lower track. \(\delta'((q,D),(Z,X))=((q',D),(Z,Y), \overline{m})\) [rewrite \(X\) to \(Y\) if on lower track]
• If \(\delta(q,X)=(q',Y,R)\) [lower track 上的分界線]
  • \(\delta'((q,U),(X,*))=((q',U),(Y,*),R)\)
  • \(\delta'((q,D),(X,*))=((q',U),(Y,*),R)\)
• If \(\delta(q,X)=(q',Y,L)\) [upper track 上的分界線]
  • \(\delta'((q,U),(X,*))=((q',D),(Y,*),L)\)
  • \(\delta'((q,D),(X,*))=((q',D),(Y,*),L)\)

Multi-Tapes TM

\(k\) 個無限長紙帶，\(k\) 個讀寫頭，\(\delta:(Q\backslash F)\times \Gamma^k \to Q\times \Gamma^k \times \{L,R\}^k\).

This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine—no matter how many tapes—can be simulated by a single-tape machine using quadratically more computation.

Nondeterministic TM

在非確定性圖靈機中，\(\delta(q,a)\) 成為一個集合 (a finite set of possibilities)。

修改 Instantaneous Description 的定義：For any current ID, there maybe finite number of possible next ID. \(x\) is accepted by non-deterministic TM iff there exists an accepting state \(q_f\) such that \(q_0 x\vdash^* \alpha q_f \beta\).

與 DFA/NFA 相同，DTM simulates NTM；其通過 BFS 遍歷 NTM 的 computation tree 直到找到對應的接受路徑。因此一般而言，與 NTM 等價的 DTM 的計算復雜度是 exponential 級別的。

Recursive Enumerable Language

• \(L\) is recursively enumerable (RE), or computably enumerable (CE), if some TM accepts the language \(L\).
• A language \(L\) is recursive, or decidable, if some TM accepts the language \(L\), and halts on all the inputs.
• A function \(f\) is partial recursive, or partially computable, if some TM computes the function (if halts on all the inputs on which \(f\) is defined, and it does not halt on inputs on which \(f\) is not defined).
• A function \(f\) is recursive, or computable, if some Turing Machine computes the function, and \(f\) is defined on all elements of \(\Sigma^*\) (圖靈機一定會停機).

Construct a Non-RE Language (Diagonal Language) \(L_d=\{w_i:w_i\notin L(M_i)\}\). Here, all Turing Machines are listed in order \(M_0,M_1,M_2,...\)

Define \(L_u\) (Universal Language) as \(L_u=\{(M,w):M \text{ accepts } w\}\). Then, \(\overline{L_u}\) is also non-RE. Proof: \(\overline{L_u}=\{(M,w): M \text{ does not accept } w\}\), therefore if there is a TM \(M\) accepting \(\overline{L_u}\), we can construct a TM \(M'\) accepting \(L_d\) using \(M\) as a subroutine.

Theorem 1. If \(L\) is recursive, then \(\overline{L}\) is recursive.

• WLOG assume Turing Machine \(M\) accepts \(L\), and there is only one accepting state.
• Create a new state \(q_{new}\).
• Construct \(M'\) accepting \(\overline{L}\) as follows: for any non-accepting state \(q\) and any letter \(a\), if \(\delta(q,a)\) is not defined in \(M\), then let \(\delta(q,a)=q_{new}\). Other transitions in \(M'\) are as in \(M\).
• Finally, let \(q_{new}\) to be the only accepting state in \(M'\).

Theorem 2. \(L\) is recursive iff \(L\) is RE and \(\overline{L}\) is RE.

\(\Rightarrow\) part: Since \(L\) is recursive, \(\overline{L}\) is also recursive (Theorem 1), therefore \(L\) and \(\overline{L}\) are both RE.

\(\Leftarrow\) part: Suppose \(M\) accepts \(L\) and \(M'\) accepts \(\overline{L}\). Construct \(M''\) as follows:

• \(M''(x)\) copies \(x\) into two different tapes.
• Then it runs parallel simulation - \(M(x)\) on the first tape, \(M'(x)\) on the second tape.
• If at any point \(M(x)\) accepts, then \(M''\) accepts. If \(M'(x)\) accepts, then \(M''\) halts and rejects.

Universal Turing Machine

Universal Turing Machine (UTM) accepts Universal Language \(L_u=\{(M,w):M\text{ accepts }w\}\).

先引入 Turing Machine 的 coding scheme:

• Denote tape symbols as \(X_1,X_2,...,X_s\) (e.g., \(X_1\) for 0, \(X_2\) for 1, \(X_3\) for blank)
• Denote directions as \(L=D_1,R=D_2\)
• Encode a transition \(\delta(q_i,X_j)=(q_k,X_l,D_m)\) as \(0^i10^j10^k10^l10^m\)
• Encode the TM as \(C_111C_211C_3...C_n\) where \(C_i\) is the \(i\)-th transition.

為使輸入字符串 \(w\) 與 \(M\) 的編碼一致，同樣將 \(w\) 按照上述方式 (1 與 3) 編碼：\(10^1\) for 0, \(10^2\) for 1, \(10^3\) for blank。

UTM has the following tapes.

• Input tape: \(M\#w\)
• Working tape: initialized with encoded \(w\). read-write head on this tape always points to \(1\)
• State tape: initialized with \(0\) (represent starting state \(q_1\))
• Scratch tape

UTM simulates \(M(x)\) as follows.

• Suppose the State tape has \(0^i\).
• Suppose the head on the Working tape is at the start of \(10^j1\).
• Search the code of \(M\) on the Input tape of the form \(0^i10^j10^k10^l10^m\), where on both sides we have either blanks or \(11\).
• Change the content of State tape to \(0^k\) (done using copying).
• Change the string from \(10^j1\) to \(10^k1\) on the Working tape. (mark the current \(1\) to a special symbol \(*\), copy the content into Scratch tape - instead of copying the portion \(*0^j1\), write \(*0^k1\), then copy the Scratch tape back to the Working tape)
• Revert the special symbol \(*\) to \(1\), move the head on the Working tape to the previous or next \(1\) depending on the value of \(m\).

When \(M\) halts, UTM can tell if it is in the single accepting state and so moves to an accepting state of its own.

Decidability

Reduction

\(P_1\) reduces to \(P_2\) (\(P_1\leq _m P_2\)) if some recursive function \(f\) behaves as follows: \(x\in P_1\) iff \(f(x)\in P_2\).

Some properties:

• If \(P_2\) is recursive, then so is \(P_1\)
• If \(P_2\) is RE, then so is \(P_1\)
• If \(P_1\) is undecidable, then so is \(P_2\)
• If \(P_1\) is non-RE, then so is \(P_2\)

TMs accepting empty set

Let \(L_e=\{M:L(M)=\emptyset\}\), \(L_{ne}=\{M:L(M)\neq \emptyset\}\).

• Theorem: \(L_{ne}\) is RE (存在 TM 只接受 non-empty TMs).
• Theorem: \(L_e\) is not recursive.
• Corollary: \(L_e\) is not RE (不存在 TM 只接受 empty TMs).

Proof of \(L_{ne}\) is RE: Construct \(M'\) to accept \(M\) that \(L(M)\neq \emptyset\).

Step 上界 \(t\) 的引入保證 \(M'\) 在輸入某個 \(L(M)\neq \emptyset\) 的 \(M\) 時不會陷入無限循環。

Proof of \(L_e\) is not RE: Reduce \(\overline{L_u}\) to \(L_e\). Given the input \(M\#w\), construct a non-input TM \(M'\) (沒有輸入，或者說輸入 \(x\) 不影響輸出)

注意 \(M'\) 這一圖靈機是否接受輸入 \(x\) 與 \(x\) 本身無關；它僅與 \(w\in L(M)\) 有關。

• 若 \(w\in L(M)\)，即 \(M\# w\notin \overline{L_u}\)，\(M'\) 接受任意字符串，即 \(M'\notin L_e\)
• 若 \(w\notin L(M)\)，即 \(M\#w\in \overline{L_u}\)，\(M'\) 不接受任意字符串，即 \(M'\in L_e\)

Rice's Theorem

Suppose \(P\) is a non-trivial property about RE languages. Then \(L_p\) is undecidable.

• non-trivial property: at least one RE language satisfies \(P\), and at least one RE language doesn't satisfy \(P\).
• \(L_p=\{M|L(M) \text{ satisfies property } P\}\).

Proof.

Suppose \(P\) is a non-trivial property about RE languages. WLOG assume \(\emptyset\) satisfies \(P\) (otherwise switch \(P\) to \(\overline{P}\)). Suppose \(L\) is an RE language that does not satisfy \(P\). Let \(M''\) be the machine which accepts \(L\).

Define \(f:f(M)=M'\) as follows.

We can see that \(L_e\leq_m L_p\).

• If \(L(M)=\emptyset \in L_e\), then \(L(M')=\emptyset \in L_p\).
• If \(L(M)\neq \emptyset \notin L_e\), then \(L(M')=L\notin L_p\).

As \(L_e\) is not recursive, we have that \(L_p\) is also not recursive.

Post's Correspondence Problem

PCP: 給定兩個字符串表 (list of strings) \(A=w_1,w_2,...,w_k\) 與 \(B=x_1,x_2,...,x_k\)；波斯特對應問題的解是一個序列 \(i_1,i_2,...,i_m \ (m>0)\) 使得 \(w_{i_1}w_{i_2}...w_{i_m}=x_{i_1}x_{i_2}...x_{i_m}\)

MPCP: 在 PCP 基礎之上規定兩個字串的首個字符串是一種特定組合。舉例來說，規定必須使用 \(w_1\) 與 \(x_1\)，MPCP 的解序列將使得 \(w_1w_{i_1}w_{i_2}...w_{i_m}=x_1x_{i_1}x_{i_2}...x_{i_m}\)

Argument 1. MPCP \(\leq_m\) PCP.

對于任意 MPCP 問題，我們能夠構造一個等價的 PCP 問題；若該 PCP 問題有解，相應的 MPCP 問題亦有解。

MPCP 問題：給定 \(A=w_1,w_2,...,w_k\) 與 \(B=x_1,x_2,...,x_k\) 要求起始字符串組合為 \(w_i\) 與 \(x_j\)。按照如下方式構造 PCP 問題的字符串表 \(A'=w_0',w_1',...,w_{k+1}'\) 與 \(B=x_0',x_1',...,x_{k+1}'\)。

• \(w_i'=\) inserting \(*\) after each symbol in \(w_i\)
• \(x_i'=\) inserting \(*\) before each symbol in \(x_i\)
• \(w_0'=*w_i',x_0'=x_j'\) (靈魂)
• \(w'_{k+1}=\$\), \(x_{k+1}'=*\$\)

不得不說真的很妙。如果在 \(A',B'\) 上 PCP 有解，首先可以觀察到的是解序列一定以 \(0\) 開頭，以 \(k+1\) 結尾：這是由 \(*\) 與 \(\$\) 的巧妙安排決定的。若解序列為 \(0,i_1,i_2,...,i_m,k+1\)，那么對應的 MPCP 問題的解序列為 \(i,i_1,i_2,...,i_m\) (for \(A\)) 與 \(j,i_1,i_2,...,i_m\) (for \(B\))。

Argument 2. \(L_u\leq_m\) MPCP.

給定輸入 \(M\#w\)，我們的目的是構造一個等價的 MPCP 問題：若該 MPCP 問題有解，\(M\) 接受 \(w\)。這就將 \(L_u\) 歸約到了 MPCP 問題上。構造方式 (真的很妙啊！)

若該 MPCP 有解，我們可以看到每個由 \(\#\) 包圍起來的 section 都是某一步的 instantaneous description；并且直觀上來說，是 \(A\) 形成的字符串在「追趕」\(B\) 形成的字符串 (畢竟一開始是 \(\#\) v.s. \(\#q_0w\#\))。

什么時候算「追上」了呢？就是 \(A\) 的 ID 到達 accepting state 的時候。此時 \(A\) 中的 \(XqY,Xq, qX\) 都換一個 \(B\) 中的 \(q\)，兩者之間的差距越來越小，直到 \(A\) 中被消除到只剩一個 \(q\)；此時 \(q\#\#\) 換一個 \(B\) 中的 \(\#\)，兩字符串完全一致。

MPCP 中這一「追趕」的過程對應的正是 \(M\) 在輸入 \(w\) 上的轉移過程。具體來說，\(A\) 是前一步，\(B\) 是后一步；如果 \(A\) 最終能追趕上 \(B\) (MPCP 有解)，那么 \(M\) 也能夠到達 accepting state (\(M\) accepts \(w\))。

Undecidable CFGs

PCP 問題又可視作一個歧義語法的判斷問題。給出字符串表 \(A=w_1,...,w_k\) 與 \(B=x_1,...,x_k\)，我們再添加一個 index list \(I=\{a_1,a_2,...,a_k\}\)；其中 \(I\cap \Sigma=\emptyset\)。定義以下語法 \(G\)：

該語法又可分為兩個子語法 \(G_A\) (僅與 \(A\) 有關的部分)，\(G_B\) (僅與 \(B\) 有關的部分)；由此可以得出一系列結論鏈條：\(L(G_A)\cap L(G_B)\neq \emptyset\) iff \(G\) is ambiguous iff PCP has a solution.

很好理解：若 \(L(G_A)\cap L(G_B)\) 交集不為空，那么其中任意一個字符串的 index 部分都表示一個 PCP 問題的解；且由于 \(G\) 在 \(G_A\) 與 \(G_B\) 方向都能生成相同的字符串，說明 \(G\) 是歧義的。由于 PCP 問題的不可判定性，我們進一步證明了 \(G\) 的歧義與否與 \(L(G_A)\cap L(G_B)\) 非空與否均是不可判定的。

可以證明 \(L(G_A),L(G_B), \overline{L(G_A)}, \overline{L(G_B)}\) 均為 CFG。注意，general CFG \(G\) 取反并不一定是 CFG，是這里的特殊 CFG \(G_A,G_B\) 取反后仍為 CFG。

從 PCP 問題的不可判定開始，我們又可以引入一系列與 CFG 相關的不可判定問題：

• 給出 CFGs \(G_1\) 與 \(G_2\)，判定 \(L(G_1)\cap L(G_2)=\emptyset\)
  • 無法判定！e.g., 取 \(G_1=G_A,G_2=G_B\) 即可。
• 給出 CFGs \(G_1\) 與 \(G_2\)，判定 \(L(G_1)=L(G_2)\)
  • 無法判定！e.g., 取 \(L(G_1)=\overline{L(G_A)}\cup\overline{L(G_B)}=\overline{L(G_A)\cap L(G_B)}\)；而 \(L(G_2)\) 則是 \((\Sigma\cup I)^*\) (全集)。
• 給出 CFG \(G\) 與 RE \(R\)，判定 \(L(G)=L(R)\)
  • 無法判定！與問題 2 類似。
• Given CFGs \(G,G_1,G_2\) 與 RE \(R\)，\(L(G)=T^*,L(G_2)\subseteq L(G_1),L(R)\subseteq L(G)\) 均不可判定。

NP Problems

Complexity

TM \(M\) 的時間復雜度：

• If \(M\) is deterministic TM, \(Time_M(x)\) is the number of steps used by \(M\) on input \(x\) before halting (if \(M\) does not halt on \(x\), \(Time_M(x)=\infty\))
• If \(M\) is non-deterministic TM, \(Time_M(x)\) denotes the maximum time on any path, even non-accepting.
• If \(M\) is \(T(n)\) time bounded, \(Time_M(x)\leq T(n)\) for all \(|x|=n\).

TM \(M\) 的空間復雜度：

• \(Space_M(x)\) is the maximum number of cells touched by \(M\) on input \(x\). Usually we only consider the cells on work tapes (excluding input & output tape). If \(M\) does not halt on \(x\), \(Space_M(x)=\infty\).
• If \(M\) is \(S(n)\) space bounded, \(Space_M(x)\leq S(n)\).

為什么在計算復雜度時可以忽略常數 \(c\)？可以證明圖靈機總是可以進行 Tape Compression (空間上的常數省略) 與 Linear Speedup (時間上的常數省略)。

• Tape Compression. WLOG fix \(c>0\). If a language \(L\) is accepted by a machine \(M\), with \(k\) tapes, that is \(S(n)\) space bounded, then \(L\) is accepted by a machine \(M'\), with \(k\) tapes, that is \(\lceil c S(n)\rceil\) space bounded.
• Linear Speedup. WLOG fix \(c>0\). Suppose \(L\) is accepted by a machine \(M\), with \(k\geq 2\) tapes, that is \(T(n)\) time bounded, where \(\lim_{n\to\infty}T(n)/n=\infty\). Then \(L\) is also accepted by a machine \(M'\) that is \(\lceil cT(n)\rceil\) time bounded.

幾大 complexity class 之間的關系。

• \(\text{DTIME}(S(n))\subseteq \text{DSPACE}(S(n))\)
• If \(L\) is in \(\text{DSPACE}(S(n))\), and \(S(n)\geq \log n\), then there exists a constant \(c\), which depends on \(L\), such that \(L\) is in \(\text{DTIME}(c^{S(n)})\).
• If \(L\) is in \(\text{NTIME}(T(n))\) then there exists a constant \(c\), which depends on \(L\). such that \(L\) is in \(\text{DTIME}(c^{T(n)})\).

NP

P & NP.

• \(P=\{L|\text{ some }poly(n) \text{ bounded deterministic DTM accepts }L\}\)
• \(LP=\{L|\text{ some }poly(n)\text{ bounded NDTM accepts }L\}\)

Proposition. If \(L\in NP\), then there exists a deterministic polynomial time computable predicate \(P(x,y)\), and a polynomial \(q(\cdot)\) such that:

Proof. If \(L\in NP\), there exists a \(q(n)\) time bounded NDTM \(N\) accepting \(L\). WLOG assume that \(N\) has exactly two choices in each state (\(|\delta(q,\alpha)|=2\)), and \(y\) is a 01 string.

We verify \(P(x,y)\) as follows.

• Let \(y=y_1y_2...y_m\). If \(m>q(|x|)\), then reject.
• Otherwise simulate \(N\), where at step \(i\), choose the next state based on whether \(y_i\) is \(0\) or \(1\) (we can say \(y\) guide through \(x\)'s matching in \(N\))
• If in the end \(N\) stays in an accepting state (\(N\) accepts in the above simulation), \(P(x,y)=1\).

根據以上的 simulation，如果 \(x\in L\)，那么一定存在某個 \(y\) 滿足 \(|y|\leq q(|x|)\)，使得 \(P(x,y)=1\)。我們將這樣的 \(y\) 稱為 \(x\in L\) 的一個 certificate 或 proof。據此，有人把 NP 問題定義為 a class of languages for which "proofs" can be easily (in polynomial time) verified.

NP-Completeness

定義 reduction \(L_1\leq_m^p L_2\): there exists a poly-time computable function \(f\) such that \(x\in L_1\iff f(x)\in L_2\). The relation \(\leq_m^p\) is reflexive and transitive.

我們說 \(L\) 是 NP-complete 的當前僅當：

• \(L\in NP\)
• \(\forall L'\in NP, L'\leq_m^p L\)

NP-hard 問題僅僅滿足 (2)，不要求其是 NP 問題。

著名的 NP-complete 問題：Satisfiability (e.g., 3-SAT), 3D Matching (三分圖匹配), Vertex Cover, MAX-CUT (最大割問題), K-Clique, Independent Set, Hamiltonian Circuit, Partition, Set Cover, Traveling Salesman Problem (權重和 \(\leq B\) 的哈密頓回路)。

\(P=NP\) 問題：

• If one of the NP-complete problem is solvable in poly-time (\(\exists L\in NPC\land L\in P\)), then all the problems in NP are solvable in poly-time (\(P=NP\)).
• If \(P\neq NP\), then none of the NP-complete problems are solvable in poly-time.

將 3-SAT 問題歸約到 Vertex Cover 問題：若有 \(n\) 個變量，\(m\) 個 3-SAT clauses，構造出一個點數為 \(2n+3m\) 的圖，分別是 \(n\) 個 \(x_i\)，\(n\) 個 \(\lnot x_i\)，\(m\) 個三角形，每個三角形對應一個 clause 中的三個 literals。連邊策略很顯然：該圖的 Vertex Cover 解對應的是原 3-SAT 的一個解。

獨立集 (Independent Set) 問題：獨立集中的點兩兩不相連。給出 \(G=(V,E)\)，如果 \(G\) 有一個大小為 \(k\) 的 vertex cover，那么它有一個大小為 \(|V|-k\) 的獨立集，且 \(G'=(V,E^c)\) 有一個大小為 \(|V|-k\) 的 clique。

那么有 \(V'\) 是 \(G\) 的 vertex cover \(\iff\) \(V-V'\) 是 \(G\) 的獨立集 \(\iff\) \(V-V'\) 是 \(G'\) 的 clique。

Reference

{% note warning %}

? This article is a self-administered course note.

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

{% endnote %}

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。」