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

Posted on 繁/简： set

埃癸斯 (Aegis) 虽然是高性能的反暗影压制兵装 (Anti-Shadow Suppression Weapon)，但她在逻辑推理方面并未得到特殊强化。在辰巳人工岛的月光馆学园插班入学后，埃癸斯常常感觉自己跟不上课程进度。

埃癸斯尤其不擅的学科是计算理论 (Theory of Computation)；她认为，作为人工智慧的自己，底层是程式的逻辑；既然如此，自己无法完成计算理论作业的试题，和任何机器都解决不了停机问题是相同的原理。

作为特别课外活动部 (S.E.E.S, Specialized Extracurricular Execution Squad) 的 Leader，你察觉到埃癸斯只是在找借口。为了课外活动部的未来，你必须对她展开特别辅导。


Tutorial 1 (RegEx)

Q1. Prove \((A^*)^+=(A^+)^*=A^*\)

Note that \(\epsilon \in A^*\). Thus, \((A^*)^+=(A^*)^*\).

Also, if \(B\subseteq C\), then \(B^*\subseteq C^*\). Thus, we immediately have \(A^*\subseteq (A^+)^* \subseteq (A^*)^*=(A^*)^+\).

Hence, it suffices to show that \((A^*)^*\subseteq A^*\). Suppose \(w\in (A^*)^*\)

Let \(w_1,w_2,...,w_k\) be such that \(w=w_1w_2...w_k\) and each \(w_i\in A^*\). For each \(i\), let \(w_{i,1},w_{i,2},...,w_{i,r_i}\) be such that \(w_i=w_{i,1}w_{i,2}...w_{i,r_i}\) and each \(w_{i,j}\in A\).

Thus, we have that \(w=w_{1,1}w_{1,2}...w_{1,r_1}w_{2,1}...w_{2,r_2}...w_{k,1}...w_{k,r_k}\), where each \(w_{i,j}\in A\). Thus, \(w\in A^*\).


Tutorial 2 (DFA)

Q1. For a DFA \(A=(Q,\Sigma,\delta,q_0,F)\), let \(\hat\delta\) be as defined in class. Show that \(\hat\delta(q,xy)=\hat\delta(\hat\delta(q,x),y)\), for all strings \(x,y\) over \(\Sigma^*\), and all states \(q\in Q\).

By induction on \(|y|\). Clearly, for \(y=\epsilon\), the statement holds.

Suppose the statement holds for \(y=w\). Then for \(y=wa\), with \(a\in \Sigma\), we have, \[ \begin{aligned} \hat\delta(q,xwa)&=\delta(\hat\delta(q,xw), a) \\ &= \delta(\hat\delta(\hat\delta(q, x), w), a) \\ &= \hat\delta(\hat\delta(q,x), wa) \\ &= \hat\delta(\hat\delta(q,x),y) \end{aligned} \] Q2. Prove \(L((R+S)^*)=L((R^*S^*)^*)\), for any regular expression \(R\) and \(S\).

Showing \(\subseteq\):

\(L(R)\subseteq L(R^*S^*)\) and \(L(S)\subseteq L(R^*S^*)\), therefore \(L(R+S)\subseteq L(R^*S^*)\).

Thus \(L((R+S)^*)\subseteq L((R^*S^*)^*)\).

Showing \(\supseteq\):

\(L((R^*S^*)^*)\subseteq L(((R+S)^*(R+S)^*)^*)\subseteq L(((R+S)^*)^*)=L((R+S)^*)\).

Therefore \(L(R+S)^*=L((R^*S^*)^*)\).

Misc. Notice \(q\in \text{Eclose}(q)\). Practice DFA to RegEx.


Tutorial 3 (RL)

Q1. True or False. If \(L\) is a regular language, then \(L^R=\{x^R|x\in L\}\) is also a regular language.

First method. Given a regular expression \(S\), we show how to construct \(S^R\) such that \(L(S)^R=L(S^R)\).

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

Induction. Suppose the statement holds for \(A,B\), then for,

  • prove \(L((A+B)^R)=L(A+B)^R\) using property \((A+B)^R=A^R+B^R\)
  • prove \(L((A\cdot B)^R)=L(A\cdot B)^R\) using property \((A\cdot B)^R=B^R\cdot A^R\)
  • prove \(L((A^*)^R)=L(A^*)^R\) using property \((A^*)^R=(A^R)^*\)

Second method. Suppose \(A=(Q,\Sigma,\delta,q_0,F)\) is a DFA for \(L\). Construct an \(\epsilon\)-NFA for \(L^R\) as follows.

\(A^N=(Q\cup \{q_0'\}, \Sigma,\delta_N,q_0',\{q_0\})\), where

  • \(\delta_N(q_0',\epsilon)=F\)
  • for \(q\in Q,a\in \Sigma\), \(\delta_N(q,a)=\{q':\delta(q',a)=q\}\). Other transitions sets are \(\emptyset\).

By induction on \(|w|\) we show that, for \(q,q' \in Q\), \(\hat\delta(q,w)=q'\) iff \(q\in \delta_N(q',w^R)\). Thus \(\hat\delta(q_0,w)\in F\) iff \(q_0\in\cup_{q\in F}\hat{\delta_N}(q,w^R)\). Thus, \(A_N\) accepts \(L^R\).

Q2. True or False. If \(L_1\) is regular and \(L_2\subseteq L_1\), then \(L_2\) is regular.

Take \(L_1=\Sigma^*\), and \(L_2\) to be some non-regular subset of \(\Sigma^*\).

Acceptance is two-way: every string accepted by a DFA is in the language, and every string rejected by a DFA is not in the language.

Q3. (hard) For any language \(L\), define \(\text{HALF}(L)=\{w|(\exists u)[wu\in L \text{ and } |w|=|u|]\}\). Show that if \(L\) is regular, then \(\text{HALF}(L)\) is regular.

Let \(A=(\delta_A,Q,q_0,F)\) be a DFA for \(L\) with some alphabet \(\Sigma\).

Then define \(B\) as follows:

  • The states \(Q_B\) of \(B\) are of the form \([q,S]\) where \(q\in Q\) and \(S\subseteq Q\).
  • The initial state of \(B\) is \([q_0,F]\).
  • \(\delta_B([q,S],a)=[\delta_A(q,a),T]\) where \(T=\{p\in Q:\exists b\in \Sigma:\exists p'\in S:\delta_A(p,b)=p'\}\).
  • The accepting states of \(B\) are \(F_B=\{[q,S]:q\in S\}\).

Then we have the following invariant by construction: all reachable states \([q,S]\) after some input are such that \(q\) is the state that \(A\) would be in after reading that input, and the states in \(S\) are all those states such that there is a path from that state to an accepting state (in \(A\)) that has the same length as the input that was read.

So when we are in a state \([q,S]\) wIth \(q\in S\) after reading some input \(w_1\), we know that \(q\) is the state of \(A\) after reading \(w_1\) and as \(q\in S\) there is some input \(w_2\) with \(|w_1|=|w_2|\) that induces a path from \(q\) to an accepting state, which means that \(w_1w_2\in L\), and so \(w_1\in \text{HALF}(L)\).

Source: StackExchange - Automata | Prove that if L is regular than half(L) is regular too


Tutorial 4 (CFG)

Q1. Give a CFG for language \(L=\{w:\#(a\in w)=\#(b\in w)\}\), \(\Sigma=\{a,b\}\). \[ S\to aSb|bSa|SS|\epsilon \] Q2. Give an unambiguous CFG for the above language.

design three minimal states:

  • \(T\): balance state, where \(\#a=\#b\).
  • \(A\): imbalance state, where \(\#a=\#b+1\).
  • \(B\): imbalance state, where \(\#b=\#a +1\).

To eliminate ambiguity, we need to prevent partial derivations from achieving the state prematurely, that is, no non-empty proper prefix has the same property of the whole string. \[ \begin{aligned} &S\to \epsilon|TS \\ &T\to aB|bA \\ &A\to a|bAA \\ &B\to b|aBB \end{aligned} \] \(T\) only achieves \(\#a=\#b\) if if is fully expanded, so are \(A\), \(B\).

The recursive productions correct the initial imbalance without allowing it to balance out prematurely

参见上图，按照上述的递归结构，由位置 \((x,y)\) 开始，找到之后的第一个 \((x_T,y)\)，把 \([x,x_T]\) 划分为 \(T\)。同理，找到之后的第一个 \((x_A,y+1)\)，把 \([x,x_A]\) 划分为 \(A\)；找到之后的第一个 \((x_B,y-1)\)，把 \([x,x_B]\) 划分为 \(B\)。


Tutorial 5 (PDA)

记住以下原则：

  • 所有的 symbols 都被 consume 都需要被 consume；不存在提前「退出」。
  • 若不指定 transition，默认向 dead states 转移。
  • 对于给定的 \(L\)，DFA/NFA/PDA 接受 \(L\) 中的所有字符串，拒绝所有非 \(L\) 的字符串。

Q1. Give a NPDA for \(L=\{w|\#_a(w)>\#_b(w)\}\), \(\Sigma=\{a,b\}\).

NPDA: \((\{q_0,q_1\},\{a,b\},\{a,b,Z_0\},\delta,q_0,Z_0,\{q_1\})\), Acceptance by final state.

  • \(\delta(q_0,a,Z_0)=\{(q_0,a,aZ_0)\}\), \(\delta(q_0,b,Z_0)=\{(q_0,bZ_0)\}\)
  • \(\delta(q_0,a,b)=\{(q_0,\epsilon)\}\), \(\delta(q_0,a,a)=\{(q_0,aa)\}\)
  • \(\delta(q_0,b,a)=\{(q_0,\epsilon)\}\), \(\delta(q_0,b,b)=\{(q_0,bb)\}\)
  • \(\delta(q_0,\epsilon,a)=\{(q_1,\epsilon)\}\)

Q2. Give a NPDA for \(L=\{a^ib^jc^k|i=j \text{ or }j=k\}\), \(\Sigma=\{a,b,c\}\).

NPDA: \((\{q_0,q_1,...,q_7\},\{a,b,c\}, \{a,b,Z_0\},\delta,q_0,Z_0,\{q_3,q_7\})\), Acceptance by final state.

  • \(\delta(q_0,\epsilon,Z_0)=\{(q_1,Z_0), (q_4,Z_0)\}\) (non-deterministically check \(i=j\) or \(j=k\)?)
  • \(\delta(q_1,\epsilon,Z_0)=\{(q_3,Z_0)\}\) (check \(i=j=0\))
  • \(\delta(q_1,a,Z_0)=\{(q_1,aZ_0)\}\), \(\delta(q_1,a,a)=\{(q_1,aa)\}\) (check \(i\))
  • \(\delta(q_1,b,a)=\{(q_2,\epsilon\}\), \(\delta(q_2,b,a)=\{(q_2,\epsilon)\}\) (check \(i=j\))
  • \(\delta(q_2,\epsilon,Z_0)=\{(q_3,Z_0)\}\), \(\delta(q_3,c,Z_0)=\{(q_3,Z_0)\}\) (ensure only \(c\) appears in the last part)
  • \(\delta(q_4,a,Z_0)=\{(q_4,Z_0)\}\) (ensure only \(a\) appears in the first part)
  • \(\delta(q_4,\epsilon,Z_0)=\{(q_7,Z_0)\}\) (check \(j=k=0\))
  • \(\delta(q_4,b,Z_0)=\{(q_5,bZ_0)\}\), \(\delta(q_5,b,b)=\{(q_5,bb)\}\) (check \(j\))
  • \(\delta(q_5,c,b)=\{(q_6,\epsilon)\}\), \(\delta(q_6,c,b)=\{(q_6,\epsilon)\}\), \(\delta(q_6,\epsilon,Z_0)=\{(q_7,\epsilon)\}\) (check \(j=k\))

Q3. Give a NPDA for \(L=\{w_1cw_2|w_1,w_2\in\{a,b\}^* \text{ and } w_1\neq w_2^R\}\), \(\Sigma=\{a,b,c\}\).

三种情况：

  • \(w_1,w_2^R\) mismatch.
  • \(|w_1|>|w_2^R|\) but matched before - some symbols will remain in the stack.
  • \(|w_1|<|w_2^R|\) but matched before - consume more symbols when the stack is already empty.

NPDA: \((\{q_0,q_1,q_2\},\{a,b,c\}, \{a,b,Z_0\}, \delta,q_0,Z_0,\{q_2,q_3\})\), Acceptance by final state.

  • \(\delta(q_0,a,Z)=\{(q_0,aZ)\}\), \(\delta(q_0,b,Z)=\{(q_0,bZ)\}\), for \(Z\in \{a,b,Z_0\}\) (record \(w_1\))
  • \(\delta(q_0,c,Z)=\{(q_1,Z)\}\), for \(Z\in\{a,b,Z_0\}\)
  • \(\delta(q_1,a,a)=\{(q_1,\epsilon)\}\), \(\delta(q_1,b,b)=\{(q_1,\epsilon)\}\) (match \(w_2^R\) with \(w_1\))
  • \(\delta(q_1,a,b)=\{(q_2,\epsilon)\}\), \(\delta(q_1,b,a)=\{(q_2,\epsilon)\}\) (cond. 1 - accept, but need to consume the whole string)
  • \(\delta(q_1,a,Z_0)=\{(q_2,Z_0)\}\), \(\delta(q_1,b,Z_0)=\{(q_2,Z_0)\}\) (cond. 3)
  • \(\delta(q_1,\epsilon,a)=\{(q_3,\epsilon)\}\), \(\delta(q_1,\epsilon,b)=\{(q_3,\epsilon)\}\) (cond. 2)
  • \(\delta(q_2,a,X)=\{(q_2,X)\}\), \(\delta(q_2,b,X)=\{(q_2,X)\}\), for \(X\in\{a,b,Z_0\}\)

\(q_2\): accept, but can consume more symbols. \(q_3\): accept, but must not consume any symbol (or go to dead states).

Q4. Formally defina a two stack NPDA. Is it more powerful than one stack NPDA, that is, can it accept something which cannot be accepted by one stack NPDA?

A two stack NPDA \((Q,\Sigma,\Gamma_1,\Gamma_2,\delta,q_0,Z_0,Y_0,F)\), where \(Z_0\in \Gamma_1,Y_0\in\Gamma_2\) are the initial symbols on the two stacks. Transition function \(\delta\) maps from \(Q\times\Sigma\cap\{\epsilon\}\times \Gamma_1\times \Gamma_2\) to a subset of \(Q\times \Gamma_1^*\times \Gamma_2^*\).

Intuitively, \(\delta(q,a,X,Y)\) containing \((p, \alpha,\beta)\) means that when the two stack NPDA consumes \(a\) from the input, has \(X\) and \(Y\) on the top of the first and second stack, then it goes to state \(p\) while pushing \(\alpha\) and \(\beta\) on the two stacks respectively, after popping \(X\) and \(Y\) from the stacks.

Instantaneous description of two stack NPDA: \((q,aw,X\alpha,Y\beta)\vdash (p,w,\alpha'\alpha,\beta'\beta)\), if \(\delta(q,a,X,Y)\) contains \((p,\alpha',\beta')\). \(ID\vdash^*ID'\) can then be defined by considering \(0\) or more steps of \(\vdash\).

\(L(NPDA)=\{w:(q_0,w,Z_0,Y_0)\vdash^* (q_f,\epsilon,\alpha,\beta):q_f\in F, \alpha\in\Gamma_1^*,\beta\in\Gamma_2^*\}\), Acceptance by final state,

Two stack NPDA can accept \(\{a^nb^nc^n:n\geq 0\}\) (not context-free) while one stack NPDA cannot. Two stack NPDA accepts it by first pushing \(a\)'s in both the stacks, and then comparing \(b\)'s in the first stack and then comparing \(c\)'s in the second stack. In fact, two stacks are enough to simulate a Turing Machine, and thus is as powerful as any computing device.


Tutorial 6 (Chomsky Normal Form)

Eliminate useless symbols 时，一定是先 remove non-generating symbols, 再 remove unreachable symbols；顺序很重要。

Q1. \(L=\{\alpha\alpha:\alpha\in \{a,b\}^*\}\) is not a CFL.

Suppose by way of contradiction that \(L\) is a CFL. Then, let \(n>1\) be as in the pumping lemma. Now consider \(z=a^{n+1}b^{n+1}a^{n+1}b^{n+1}\). Let \(z=uvwxy\) be as in the pumping lemma.

Case 1: \(vwx\) is contained in either \(a^{n+1}\) or \(b^{n+1}\). (very obvious)

Case 2: \(vwx\) is contained in the first \(a^{n+1}b^{n+1}\). In this case, \(uwy\) is of the form \(a^{n+1-k}b^{n+1-s}a^{n+1}b^{n+1}\), where \(vx=a^kb^s\), and thus \(0<k+s\leq n\). Let \(i=0\), we check whether \(uwy\in L\).

It cannot be written as \(\alpha\alpha\). Suppose otherwise, then the second \(\alpha\) must end with \(b^{n+1}\) (as \(|\alpha|=\frac{4n+4-k-s}{2}>n\)). Thus, the first \(\alpha\) ends somewhere in the first sequence of \(b\)'s: \(b^{n+1-s}\).

Thus, the second \(\alpha\) ends with \(a^{n+1}b^{n+1}\).

But this means \(|\alpha|\geq 2n+2\), and thus \(k+s\leq 0\), a contradiction.

Case 3: \(vwx\) is contained in \(b^{n+1}a^{n+1}\) part of \(z\) (same logic as case 2).

Case 4: \(vwx\) is contained in the second \(a^{n+1}b^{n+1}\) part of \(z\) (same logic as case 2).

Q2. Prove that \(L=\{w:w\in \{a,b,c\}^* \text{ and } \#_a(w)=\#_b(w)=\#_c(w)\}\) is not a CFL.

Suppose by way of contradiction that \(L\) is a CFL.

Given a regular language \(R=a^*b^*c^*\), by the closure property of CFL, \(L\cap a^*b^*c^*=\{a^nb^nc^n:n\geq0\}\) would also be a CFL, which leads to a contradiction. (单栈 PDA 不能处理三个长度相等的符号)


Tutorial 7 (CFL)

Q1. Prove or disprove that the language \(\{a^ib^jc^kd^l|i=0\text{ or } j=k=l\}\).

Suppose by way of contradiction, otherwise. Consider the intersection of the language in the question with \(\{ab^jc^kd^l|j=k=l\}\) must be context-free.

Consider the substitution, \(s(a)=\epsilon,s(b)=a, s(c)=b, s(d)=c\). The resulting language \(\{a^jb^kc^l|j=k=l\}\) must be context-free. Contradiction.

Thus, the language given in question is not context-free.

Q2. Prove or disprove that the language \(\{udv:u,v\in\{a,b,c\}^*\text{ and } u \text{ is a substring of }v\}\).

上一道题是构造 \(a^nb^nc^n\)，这一道题则是构造 \(\alpha\alpha\)。

Suppose by way of contradiction, otherwise. Let \(L'=L\cap c\{a,b\}^* cdc\{a,b\}^*c\), then, the intersection \(L'=\{cwcdcwc:w\in \{a,b\}^*\}\) must be context free.

Now considering the substitution, \(s(c)=s(d)=\epsilon, s(a)=a, s(b)=b\), and \(s(L')=\{ww:w\in \{a,b\}^*\}\) must be context-free. Contradiction.

Thus, the language given in question is not context-free.

Q3. For a language \(L\), Let \(Prefix(L)=\{x:(\exists y)[xy\in L]\}\). Prove or disprove: If \(L\) is context-free, then \(Prefix(L)\) is also context-free.

Suppose \((V,\Sigma,S,P)\) is the Chomsky Normal grammar for \(L\) without any useless symbols. The new grammar for \(Prefix(L)\) is \((V\cup \{A^p:A\in V\},\Sigma,S^p,P')\), where \(P'\) is defined as follows.

Intuitively, \(A^p\) generates prefixes of all strings which are generated by \(A\).

  • For each production \(A\to \alpha\) in \(P\).
    • \(A\to \alpha\) is in \(P'\)
    • \(A^p\to \alpha\) is in \(P'\)
  • For each production \(A\to BC\) in \(P\).
    • \(A\to B^p\) is in \(P'\)
    • \(A\to BC^p\) is in \(P'\)

We then remove all unit-productions in \(P'\), this will result in a Chomsky Normal form grammar for \(Prefix(L)\). Therefore, \(Prefix(L)\) is also context-free.

Q4. Prove Odgen's Lemma: Let \(L\) be a CFL, then there exists a constant \(n\) such that the following holds for any string \(z\) of length at least \(n\) in \(L\). If we mark at least \(n\) positions in \(z\) to be distinguished, then we can write \(z=uvwxy\) such that:

  • \(vwx\) has at most \(n\) distinguished positions.
  • \(vw\) has at least one distinguished position.
  • For all \(i\), \(uv^iwx^iy\in L\).

Proof. (只取精髓部分) Let \(m\) be the number of non-terminals, \(n=2^{m+1}\).

Consider the derivation tree of \(z\). Suppose we've converted the grammar to Chomsky Normal Form, the tree is binary. Call any node of \(s\) a branch point if both of its sons have distinguished descendents.

Claim. There exists a path with at least \(k+1\) branch points on the path. We start at the top,

  • If only one son of a node has distinguished descendants, then go in the direction of that son.
  • If both sons of a node have distinguished descendants, then go in the direction of the son with more distinguished descendants.

第二种节点均为 branch points。并且，每经过一个 branch point，distinguished descendants 的数量最多会减少一半。因此，该路径上 branch points 的数量 \(\geq \log 2^{m+1}=m+1\)。考虑取该路径上的最后 \(m+1\) 个 branch points；根据鸽巢原理，至少存在两个 branch points 对应的是同一个 non-terminal state。

剩余证明见 Uchicago 280000-1 Lec.10.

Q5. Use Ogden's Lemma to show that \(\{0^r1^s2^t|r=s\text{ and } s\neq t\}\) is not context-free.

想到了，但没完全想到。

Consider the string \(z=0^n1^n2^{n!+n}\). Let \(0\)'s be distinguished positions. Let \(z=uvwxy\). Note that if \(v\) or \(x\) contain two distinct symbols from \(\{0,1,2\}\), then clearly \(uv^2wx^2y\notin L\). Thus, \(v\in 0^*\). Furthermore, if \(x\notin 1^+\) or if \(|x|\neq |v|\), then, \(uv^2wx^2y\) contains different number of \(0\)'s than \(1\)'s. Thus, we have that \(|v|=|x|>0\), and \(v\in 0^+, x\in 1^+\). Now, let \(m=|v|\), Then, \(uv^{1+n!/m}wx^{1+n!/m}y=0^{n!+n}1^{n!+n}2^{n!+n}\notin L\). A contradiction.

一直困扰着我的问题的答案 (\(x\) 同时 contains \(2\) 和 \(3\)，pump 以后总是能保证 \(s\neq t\) 怎么办？)

This guy is a genius


Tutorial 8 (Turing Machine I)

Q1. Given a Turing Machine which converts a binary number to equivalent unary number.

Following is a two-tape machine. 2nd tape is used only for writing \(1\), so symbol read there does not matter. On the 1st tape, the start state is \(q_0\):

  • In state \(q_0\): we move to the right end of input, and go to state \(q_1\)
  • In state \(q_1\): mimic subtraction by \(1\), rewrite \(...10^i\) to \(...01^i\), append another \(1\) on the 2nd tape, and go back to \(q_0\)
\((0,X)\) \((1,X)\) \((B,X)\)
\(q_0\) \(q_0\), \((0,X)\), \((R,S)\) \(q_0\), \((1,X)\), \((R,S)\) \(q_1\), \((B,X)\), \((L,S)\)
\(q_1\) \(q_1\), \((1,X)\), \((L,S)\) \(q_0\), \((0,1)\), \((R,R)\) Halt

Q2. Design a Turing Machine to accept \(\{a^n|n\text{ is a prime}\}\).

Tape \(1\) holds \(n\), and tape \(2\) holds the divisors from \(n-1\) to \(2\).

  1. Initially input \(a^n\) is in tape \(1\).
  2. In input contains only \(0\) or \(1\) \(a\), then reject.
  3. Copy input to tape \(2\).
  4. Decrement the number of \(a\)'s in tape \(2\) by \(1\).
  5. If tape \(2\) contains only one \(a\), then accept (input is a prime).
  6. Move to left end of the strings in tape \(1\) and tape \(2\).
  7. Move step by step, in both tape \(1\) and tape \(2\), to right, until one of them hits a blank.
    • If both tapes hit blank at the same time, then reject (\(n\) is divisible by that divisor).
    • If tape \(2\) hits blank first then, move to the left end of the string of tape \(2\), and go to step 7.
    • If tape \(1\) hits blank first then, go to step 4 (\(n\) is not divisible by current divisor).

Q3. Consider any partial function \(f\), and define a language \(L_f=\{x\#y|x\in\text{domain}(f) \text{ and } f(x)=y\}\). Show that \(f\) is partial recursive if \(L_f\) is RE.

Suppose \(M'\) is the machine which accepts \(L_f\), then \(M\) on input \(x\) uses the following algorithm to determine its answer. \[ \begin{aligned} &\text{For } t=0 \text{ to }\infty \\ &\text{For all } y \text{ of length at most }t \\ & \ \ \ \ \ \ \ \ \text{If } M'\text{ accepts } x\#y \text{ within } t\text{ steps, then output } y \\ &\text{EndFor} \\ &\text{EndFor} \end{aligned} \] To check whether \(M'\) accepts \(x\#y\) within \(t\) steps, we can introduce a new counter tape and place \(t\) in unary on that tape, and place the head of the tape at the beginning of the number. In each step of \(M'\), one moves the head right. If \(M'\) accepts before reaching the blank at the end of \(t\), then we knoe that it accepts within \(t\) steps.

Also note that \(M\) needs to keep a copy of \(x\#y\) before simulating \(M'\).

重点：除了枚举 \(y\) 之外，为什么要枚举一个步数上界 \(t\)？如果选择的 \(y\) 是错的，\(M'\) 可能不会停机！

Q4. Is a 2-stack non-deterministic PDA as powerful as non-deterministic TM?

这道题最复杂的部分想出来了，就只简单的写一些。

  • 2-stack NPDA \(\Rightarrow\) NTM: ID \(\alpha q\beta\) of TM will be represented in the 2-NPDA by keeping \(\alpha\) in stack 1 (with first letter of \(\alpha\) at the bottom of stack) and \(\beta\) in stack 2 (with first letter of \(\beta\) at the top of stack). Stack starting symbol \(Z\) represents surrounding blanks.
  • NTM \(\Rightarrow\) 2-stack NPDA: Use two working tape, simulating two stacks respectively. The head of each tape represents the top of the stack.


Tutorial 9 (Turing Machine II)

Q1. Let \(L_5=\{M:L(M)\text{ has }\leq 5 \text{ elements}\}\), show how to reduce \(L_e\) to \(L_5\).

注意，这门课中 reduction 概念似乎与 COMP3357 不太一样；重要的是找到这一映射函数 \(f\)，满足对于任意 \(x\in L_e\)，\(f(x)\in L_5\)；对于任意 \(x \notin L_e\)，\(f(x)\notin L_5\)。 \[ \begin{aligned} &f: M\to M' \\ &M'(x) \\ &\text{For }t=0 \text{ to } \infty \\ &\text{For }i=0 \text{ to } t \\ &\ \ \ \ \ \ \ \ \text{If } M(w_i) \text{ accepts within }t \text{ steps, then accept} \\ &\text{Endfor} \\ &\text{Endfor} \\ \end{aligned} \] 给定 \(M\)，构造 \(M'\)；若 \(M\in L_e\)，\(M'\) 不接受任何输入，因此 \(L(M')=\emptyset\leq 5\)，\(M'\in L_5\)；若 \(M\notin L_e\)，\(M'\) 接受任何输入，因此 \(L(M')=\Sigma^* >5\)，\(M'\notin L_5\)。

Q2. 分 (a), (b), (c), (d) 四小问。

(a). Show that every finite language is recursive.

Every finite language is regular, and thus context-free and recursive.

(b). 太简单，\(L\) is recursive iff \(\overline{L}\) is recursive.

(c). Suppose that \(L\) is a recursive language and \(D\) is a finite language. Then show that \(L\triangle D\) must be recursive. (\(\triangle\) denotes symmetric difference: \(L\triangle D=(L-D)\cup (D-L)\))

使用 (a) 中的结论，\(D\) 既然 finite，一定 recursive。所以 \(L,D,\overline{L}, \overline{D}\) 均是 recursive 的。不难发现 \(L-D=L\cap \overline{D}\), \(D-L=D\cap\overline{L}\)，再利用 recursive 在 and, or 下的 closure，证明 \(\triangle\) 同样也 closure。

(d). Suppose \(L\) is a recursively enumerable language which is not recursive. Suppose \(M\) is a Turing Machine which accepts \(L\). Then show that there must be infinitely many inputs on which \(M\) does not halt.

Suppose by way of contradiction that \(M\) halts on all but finitely many inputs. Suppose \(D\) is the set of finitely many inputs on which \(M\) does not halt. Define \(M'(x)\) as follows: \[ \begin{aligned} &M'(x): \\ &\ \ \ \ \ \ \text{If } x\in D, \text{then halt and reject}. \\ &\ \ \ \ \ \ \text{If }x\notin D, \text{then simulate } M(x). \text{Accept/Reject iff } M(x) \text{ accepts/rejects}. \\ &\text{End} \end{aligned} \] 我们构造出的 \(M'\) 总会停机，且只接受 \(L\)，这与 \(L\) 是 RE 的前提冲突。据反证法，\(M\) 所不能停机的输入是无限的。

Q3. (证明停机问题不可判定！) Halting Problem is defined as follows. Given input \(i,j\), does \(M_i\) halt on input \(w_j\)? Show that the halting problem is not decidable.

Suppose by way of contradiction that halting problem is decidable. Thus there exists a Turing Machine \(H\) that can accept \(L=\{(i,j):M_i\text{ halts on }w_j\}\).

Construct a paradoxical Turing Machine \(D\): It takes an index \(k\), then simualtes \(H(k,k)\).

  • If \(H\) accepts \((k,k)\), i.e, \(M_k\) halts on \(w_k\), then \(D\) enters an infinite loop.
  • If \(H\) rejects \((k,k)\), i.e., \(M_k\) does not halt on \(w_k\), then \(D\) halts.

Since \(D\) is also a Turing Machine, it has its corresponding index \(d\). Let's now analyze the case of \(D\) taking \(d\) as an input.

  • If \(D\) does not halt on \(w_d\), it contradicts to \(H\)'s output that \((M_d,w_d)=(D,w_d)\) is accepted.
  • If \(D\) halts on \(w_d\), i.e., \(D\) halts on \(w_d\), it contradicts to \(H\)'s output that \((W,w_d)\) is rejected.

A contradiction. Therefore the Halting Problem is not decidable.


Tutorial 10 (Decidability)

Q1. \(W_i\) denotes the language accepted by the TM with code \(i\), that is \(W_i=L(M_i)\). Alphabet of the machine is \(\Sigma=\{a,b\}\), \(w_i\) denotes the \(i\)-th string (that is, string with code \(i\)). Show that \(L=\{1^i|W_i\text{ is infinite}\}\) is not RE.

WLOG rewrite \(L=\{M_i|L(M_i)\text{ is infinite}\}\).

Construct \(M'\) as follows.

\(M'(x)\) Suppose \(t\) is such that \(w_t=x\).

  • If there exists a \(j\leq t\) such that \(M(w_j)\) accepts within \(t\) steps, then reject.
  • Otherwise accept.

If \(M\in L_e\), \(M'\) accepts any string, thus \(M'=\Sigma^*\in L_{inf}\). If \(M\notin L_e\), \(M'\) is finite (if \(M\) accepts some string \(w_j\) within \(t\) steps, it will rejects all \(w_{k}\) that \(k\geq t\)), thus \(M'\notin L_{inf}\).

Q2. Given two DFA's \(M\) and \(M'\), is \(L(M)\cap L(M')=\emptyset\) decidable?

学 PCP 学傻了。我的傻瓜解：DFA 是 regular，自然也是 CFG，那么 \(L(M)\cap L(M')=\emptyset\) 自然是 not decidable 的。

然而 \(L(M)\cap L(M')=\emptyset\) 不可决定是对于 general CFG 而言的。这个问题很明显能通过构造 \(M''\) 接受 \(L(M)\) 与 \(L(M')\) 的交集进行判定。我在想什么！

Q3. Given a TM \(M'\), and a DFA \(M\), is \(L(M')\cap L(M)=\emptyset\).

能够构造出 parallel simulation 不代表其为空是 decidable 的！Construct \(M''\) as follows. \(M''(x)\):

  • Simulates \(M'\) on \(w\) and
  • Simultaneously checks if \(w\) is accepted by \(M\)

\(M''(x)\) 接受 \(L(M')\cap L(M)\)：\(M''\) can be as general as any TM, therefore deciding \(L(M'')=\emptyset\) is equivalent to deciding whther a general TM \(M''\in L_{e}\). Not decidable.

Q4. Prove or disprove: If \(L^*\) is recursive, then \(L\) is recursive.

No.

Consider the following counterexample \(L=\{0,1\}\cup \{0^i1^j:M_i\text{ halts on }w_j\}\). \(L\) is an extension of halting problem, therefore it is undecidable.

However, \(L^*=\{0,1\}^*\), this language is decidable, even regular.


Tutorial 11/12 (Complexity)

Q1. Show that the following problem is NP-complete:

  • INSTANCE: A number of \(k\) of processors, and a set \(J=\{J_1,J_2,...,J_r\}\) of jobs where job \(J_i\) has running time \(T_i\), and an overall deadline \(D\).
  • QUESTION: Is there a way to schedule the jobs on the \(k\)-processors (non-preemptively, i.e., a job has to run on the processor it is allocated to until completion) such that the total time taken to finish all the jobs is at most \(D\)?

NP (不要忘记这一步！): It is easy to see that the processor scheduling problem is in NP. Just guess a schedule (i.e., assignment of jobs to processors), and verify that each job is assigned to some processor and each processor's load is at most \(D\).

NP hardness: we reduce the partition problem to processor scheduling problem.

Given partition problem \(A=\{a_1,a_2,...,a_n\}\), where \(s(a)\) denotes the size of \(a\in A\).

Then, construct the processor scheduling problem as follows.

There are \(k=2\) processors. \(J=A=\{a_1,a_2,...,a_n\}\), and the time \(T_i\) taken for job \(a_i\in J\) is \(s(a_i)\). The deadline is \([\sum_{a\in A}s(a)/2]\).

Now it is easy to verify that there is an equal partition of \(A\) iff the job scheduling problem has a solution.

Q2. Show that \(\text{DSPACE}(n^2)\) is a proper subset of \(\text{DSPACE}(n^3)\).

Space Hierarchy: Suppose \(S_2(n)\) and \(S_1(n)\) are both \(\geq \log n\), \(S_2(n)\) is fully space constructible and \[ \lim_{n\to\infty} \frac{S_1(n)}{S_2(n)}=0 \] Then there is a language in \(\text{DSAPCE}(S_2(n))-\text{DSAPCE}(S_1(n))\)

\(n^3\) is fully space constructible as it can be computed within space \(n^3\).

As \(\lim_{n\to\infty}\frac{n^2}{n^3}=0\), using space hierarcy theorem, we have that \(\text{DSPACE}(n^3)-\text{DSPACE}(n^2)\neq \emptyset\). As trivially, \(\text{DSPACE}(n^2)\subseteq \text{DSPACE}(n^3)\).

Time Hierarchy: Suppose \(T_1(n)\) and \(T_2(n)\) are both \(\geq (1+\epsilon)n\), \(T_2(n)\) is fully time constructible and \[ \lim_{n\to\infty} \frac{T_1(n)*\log(T_1(n))}{T_2(n)}=0 \] Then there is a language in \(\text{DTIME}(T_2(n))-\text{DTIME}(T_1(n))\)


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

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