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

埃癸斯 (*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,

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

参见上图，按照上述的递归结构，由位置 \((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 不能处理三个长度相等的符号)