本篇是看完公开课后做的课程作业，答案没有对，希望我写的东西是对的。
由于是跟着英语教材做的，发上来就不想用英语，所以答案存在中英混杂的情况；由于懒得插图，所以以数学描述为主，也会缺一部分严格的叙述。
题目使用的教材是 Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Thomson Course Technology, 2006. ISBN: 0534950973.
本人用作参考的教材为该书的第三版
有限自动机 Finite Automaton
1.32 Parallel Addition
Q: 定义 \[ \Sigma_3=\left\{ \begin{bmatrix}0\\0\\0\end{bmatrix},\begin{bmatrix}0\\0\\1\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \cdots,\begin{bmatrix}1\\1\\1\end{bmatrix} \right\} \]
\[ B=\left\{w\in\Sigma_3^* \mid 第三行对应二进制数为前两行对应二进制数之和\right\} \]
证明 \(B\) 是正则 (regular) 的
Proof:
考虑 \(w^R\), 首先构造一个对应\(B^R\)的有限自动机：\(M_1=(Q, \Sigma,\delta,q_s,F)\)
其中，\(Q=\{q_c,q_{nc},q_{f}\},\ \Sigma=\Sigma_3, \ F=\{q_{nc}\},\ q_s=q_nc\)
并定义转移\(\delta: Q\times\Sigma_3\to Q\)
依次列出\(q_f\)转移： \[ \forall c\in\Sigma_3,\ \delta(q_f,c)= q_f\\ \] \(q_{nc}\)转移： \[ \forall c\in\left\{ \begin{bmatrix}0\\0\\0\end{bmatrix}, \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\0\\1\end{bmatrix} \right\},\ \delta(q_{nc},c)=q_{nc};\ \forall c\in\left\{ \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}1\\0\\0\end{bmatrix}, \begin{bmatrix}1\\1\\1\end{bmatrix}, \begin{bmatrix}0\\0\\1\end{bmatrix} \right\},\delta(q_{nc},c)=q_{f};\ if\ c=\begin{bmatrix}1\\1\\0\end{bmatrix},\delta(q_{nc},c)=q_{c} \] \(q_c\)转移： \[ \forall c\in\left\{ \begin{bmatrix}1\\1\\1\end{bmatrix}, \begin{bmatrix}0\\1\\0\end{bmatrix}, \begin{bmatrix}1\\0\\0\end{bmatrix} \right\},\ \delta(q_{c},c)=q_{c};\ \forall c\in\left\{ \begin{bmatrix}0\\1\\1\end{bmatrix}, \begin{bmatrix}1\\0\\1\end{bmatrix}, \begin{bmatrix}1\\1\\0\end{bmatrix}, \begin{bmatrix}0\\0\\0\end{bmatrix} \right\},\delta(q_{c},c)=q_{f};\ if\ c=\begin{bmatrix}0\\0\\1\end{bmatrix},\delta(q_{c},c)=q_{nc} \] 具体而言，这一构造的状态\(q_c\)表明前一次加法发生了进位，\(q_{nc}\)表示前一次加法没有发生进位，\(q_f\)表示其中某位的加法结果不正确。通过模拟二进制加法的过程，构造了可以识别\(B^R\)的自动机。
利用结论，由于\(B^R\)是正规的，得到\(B\)也是正规的 (可以翻转自动机转移，改建为NFA证明)
1.41 Perfect Shuffle
Q: 对于两个语言\(A,\ B\)，定义他们的Perfect Shuffle为 : \[ L=\left\{w\mid w=a_1b_1\cdots a_kb_k, \text{ where } a_j\in A\text{ and } b_j\in B\text{ for }j\in[1,k],\text{ each }a_i,b_i\in\Sigma\right\} \] 证明Regular Language在Perfect Shuffle下是封闭的
Proof: 设自动机\(M_A,\ M_B\)分别能够识别语言\(A,\ B\)，记\(M_A=(Q_A, \Sigma,\delta_A,q_{sA},F_A)\)，\(M_A=(Q_B, \Sigma,\delta_B,q_{sB},F_B)\)
构造新的自动机\(M=(Q,\Sigma,\delta,q_s,F)\)
其中，\(Q=Q_A\times Q_B\times \{0,1\},\ q_s=(q_{sA},q_{sB},0),\ F=F_A\times F_B\times \{1\}\)
并定义转移\(\delta:Q\times\Sigma\to Q :\)
\(\forall q_A\in Q_A,\ q_B\in Q_B,\ c\in\Sigma:\ \delta((q_{A},q_{B},0),c)=(\delta_A(q_A,c),q_B,1),\ \delta((q_A,q_B,1))=(q_A,\delta_B(q_B,c),0)\)
这一转移相当于交替地对两种语言对应的自动机进行模拟，并接受含有偶数个字符，且模拟的两个自动机均处于接受状态的字符串。
该自动机可以识别两个语言的Perfect Shuffle。
1.53 Sequential addition
Q: 定义字符集\(\Sigma=\{0,1,+,=\}\)，定义语言: \(ADD=\{x=y+z\mid x,y,z是二进制整数，同时等式成立\}\) ，证明该语言不是正则的。
Proof:
利用 Pumping Lemma , 若语言正则，设有一足够长的字符串 \(s\in ADD\)，同时满足\(s\)中三个二进制整数 \(x,\ y,\ z\) 最高位均为1，我们证明其不满足 Pumping Lemma 。
若 \(ADD\) 为正则语言，则必存在一种字符串\(s\)的分割 \(s=s_1s_2s_3\)，使得 \(s'=s_1s_2s_2s_3\in ADD\)，且\(|s_2|\neq 0\)
下面讨论\(s_2\)的形式：
若 \(s_2\) 含有 \(+\) 或 \(\times\) ，这将导致形成的新串 \(s'\) 包含多个 \(+\) 或 \(\times\)，导致 \(s'\notin ADD\)。
这表明， \(s_2\) 必须是三个二进制数 \(x,y,z\) 之一的子串。不失一般性地，我们假设\(s_2\)为\(x\)的子串
假设 \(x=x_1s_2x_3\) ，并有复制后的 \(x'=x_1s_2s_2x_3\)。
考虑到 \(|s_2|>0\) ，当\(|x_1|>0\)时，重复\(s_2\)将导致数串有效位数增加，进而使得 \(x<x'\)
当 \(|x_1|=0\) 时，\(s_2\)的最高位为1，将其重复即在原数\(x\)的左侧添加一个非零的数串，同样使得数值上\(x<x'\)
于是 \(y+z=x<x'\)，从而\(s'\notin ADD\)
当\(s_2\)为\(y\)或\(z\)的子串时，由于其仍然只改变等式中三个值中的一个，同样使得等式不成立，导致新串不属于语言\(ADD\)
综上所述，语言\(ADD\)并非正则语言。
1.60 Small NFA Construction for Large DFA
Q: 构造一个 NFA , 满足字符串右端第\(k\)个字符为 \(\mathrm{a}\) ，其中字符集为\(\{\mathrm{a},\mathrm{b}\}\)，要求状态数为\(k+1\)
A: 设 NFA: \(M=(Q,\Sigma,\delta,q_0,F)\)，其中记 \(Q=\{q_0,q_1,\cdots,q_k\}\)，\(F=\{q_k\}\)
转移 \(\delta\) 定义为 : \[ \begin{aligned} \delta(q_0,a) &= \{q_1,q_0\}&\\ \delta(q_j,a) &= \{q_1,q_{j+1}\},&\ j = 1,2,\cdots,k-1\\ \delta(q_{k},a)&=\{q_0,q_1\}&\\ \delta(q_0,b) &= \{q_0\}&\\ \delta(q_j,b) &= \{q_{j+1}\},\ &j = 1,2,\cdots,k-1\\ \delta(q_{k},b)&=\{q_0\}&\\ \end{aligned} \] 其可以识别题设语言。
1.61 Large DFA States Lower bound proof
Q: 证明可以识别 1.60 中语言的 DFA 至少有 \(2^k\) 个状态
Proof:
记题设语言为\(L\)
设有两个长为 \(k\) 的字符串\(s_1,\ s_2\)，假设 \(s_1,s_2\) 在第\(i\)位上不同，\(i\in\{1,2,3,\cdots,k\}\)；设 \(s_1\) 的第 \(i\) 个字符为 \(\mathrm{a}\) ，而\(s_2\)的第\(i\)个字符为 \(\mathrm{b}\)。
设一个可以识别该语言的自动机 \(M\) ，将\(s_1\)输入自动机\(M\)，可设其最终状态为\(q_1\)；将\(s_2\)输入相同的自动机\(M\)，可设其最终状态为\(q_2\)。
然后，分别将由连续 \(i-1\) 个 \(\mathrm{b}\) 组成的字符串\(b_{i-1}\)输入这两个分别运行的自动机中，使得开始输入\(s_1\)的自动机转移至状态\(q_1'\)，开始输入\(s_2\)的自动机转移至状态 \(q_2'\)。
此时，输入第一个自动机的字符串\(s_1'=s_1b_{i-1}\in L\) ；输入第二个自动机的字符串\(s_2'=s_2b_{i-1}\notin L\)，由于一个状态不可能同时为accept 和 non-accept ，从而\(q_1'\neq q_2'\)
进一步由于 DFA 的转移是确定的，在同一状态输入相同的字符串，其无法转移至不同的状态，从而得到 \(q_1\neq q_2\) 。
这表明，当两个长为\(k\)的字符串有任意一个位置的字符不同时，将其输入该自动机 \(M\) 后，最终的状态也必须不同。
考虑所有长为\(k\)的字符串集合 \(\{a,b\}^k\)，有\(|\{a,b\}^k|=2^k\)，且集合内任意两个字符串至少有一个位置不同，即将该集合中的字符串分别输入自动机，最终得到的状态也一定两两不同。
因此，自动机 \(M\) 至少有 \(2^k\) 个状态。
证毕。
1.59 Synchronizing Sequence
Q: 对于一个确定有限状态自动机 \(M=(Q,\Sigma,\delta,q_0,F)\)，若存在一个序列 \(s\in\Sigma^*\) ，使得 \(\forall q\in Q,\ \delta(q,s)=q_h\)，其中 \(q_h\in Q\) 为一个确定的状态，那么称 \(s\) 为自动机 \(M\) 的同步序列。
证明，若自动机 \(M\) 具有 \(k\) 个状态，且其具有同步序列，那么一定存在一个长度小于 \(k^3\) 的同步序列 \(s\)。
Proof:
对于集合 \(A\subseteq Q\), 记 \(\delta(A, c)=\{\delta(q,c)\mid q\in A\}\) ，那么 \(s\) 为同步序列的充要条件为 \(|\delta(Q,s)|=1\)
由于已知自动机 \(M\) 有同步序列，考虑任意一个二元组\((x,y)\in Q\times Q\)，于是有： \[\exists\,s\in\Sigma^*,\ \delta((x,y),s)\in\{(q,q)\mid q\in Q\}\triangleq T\] 否则条件 \(|\delta(Q,s)|=1\) 不可能满足。
由于 \(|Q\times Q|=|Q|^2=k^2\)，并由满足 \(\delta((x,y),s_0)\in T\) 的最短的 \(s_0\) 不可能经过同一状态\((q_x,q_y)\in Q\times Q\) 两次 （否则删去两次经过\((q_x,q_y)\) 之间的子串，可以构造一个更短的满足条件的 \(s_0\)），于是\(|s|\leq |Q\times Q|-1=k^2-1<k^2\)
按如下方法构造串：
设\(Q_0=Q\)，
顺序地对\(i=0,1,2,\cdots,k-1\)进行如下操作：
若\(|Q_i|\geq 2\) ，任取 \(x_i,y_i\in Q_i,\,x\neq y\)，\(\exists\, s_i\in\Sigma^*, \delta((x,y),s_i)\in T\)，并令\(Q_{i+1}=\delta(Q_i,s)\)
若\(|Q_i|=1\) ，令\(s_i=\varnothing\)，\(Q_{i+1}=Q_i\)
此时，构造字符串 \(s=s_0s_1s_2\cdots s_{k-1}\)，则\(|s|=\sum\limits_{i=0}^{k-1}|s_i| < k\cdot k^2=k^3\)，且\(|\delta(Q,s)|=1\)
证毕。
Context-Free Languages
2.27 Tricky CFL
Q: 考虑语言 \(E=\{a^ib^j\mid i\neq j ,\ 2i\neq j\}\)，证明其为 CFL
Proof:
将语言分解为\(E=\{a^ib^j\mid j<i\}\cup \{a^ib^j\mid i<j<2i\}\cup \{a^ib^j\mid j>2i\}\)
构造如下的语法： \[ \begin{aligned} S&\to U_0\mid U_1 \mid U_2\\ U_0&\to AN_0 \\ N_0&\to AN_AB_\varepsilon\mid\varepsilon\\ \\ U_1&\to AAN_1BBB \\ N_1&\to A N_1 BB_\varepsilon\mid\varepsilon\\ \\ U_2&\to AN_2BBBN_B\\ N_2&\to AN_2B\mid \varepsilon\\ N_B&\to BN_B\mid \varepsilon\\ A_\varepsilon&\to a\mid \varepsilon\\ B_\varepsilon&\to b\mid \varepsilon\\ A&\to a\\ B&\to b \end{aligned} \] 以 \(U_0,\,U_1,\,U_2\) 变量引导的语法分别对应分拆后的三个子集。于是上述 CFG 可以生成语言 \(E\)。
得证语言 \(E\) 为 CFL
2.27 If-Then-Else Ambiguous Grammar
Q: 考虑语法 \(G=(V,\Sigma,R,<STMT>)\): \[ \begin{aligned} \langle STMT\rangle&\to \langle ASSIGN\rangle\mid \langle IF\ THEN\rangle\mid\langle IF\ THEN\ ELSE\rangle\\ \langle IF\ THEN\rangle &\to if\ condition\ then\ \langle STMT\rangle\\ \langle IF\ THEN\ ELSE\rangle &\to if\ condition\ then\ \langle STMT\rangle\ else \ \langle STMT\rangle\\ \langle ASSIGN\rangle&\to a:=1 \end{aligned} \] 说明它是 Ambiguous 的，并给出一个 Non-ambiguous 的语法，生成相同的语言。
A1:
考虑字串: \(if\ condition\ then\ if\ condition\ then\ a:=1 \ else\ a:=1\)
至少有两种 Parse 的方法 : \[ if\ condition\ then\ (if\ condition\ then\ a:=1\ else\ a:=1) \] \[ if\ condition\ then\ (if\ condition\ then\ a:=1)\ else \ a:= 1 \] 所以其必然是 Ambiguous 的
A2:
原语法的主要问题在于 else 在进行 reduce 的时候，无法确定其与哪一个 if 相配对；相应地，我们通过保证所有 else 均与其最相邻的 if 进行配对，消去二义性。
因此，定义新的语法 \[ \begin{aligned} \langle STMT\rangle&\to \langle ASSIGN\rangle\mid \langle IF\rangle\mid \langle IFE0\rangle\\ \langle IF\rangle &\to if\ condition\ then\ \langle IF.ST\rangle\\ \langle IF.ST\rangle&\to \langle ASSIGN\rangle\mid \langle IF\rangle\mid \langle IFE0\rangle\\ \langle IFE0\rangle&\to if\ condition\ then\ \langle IFE.ST\rangle\ else\ \langle IF.ST\rangle \\ \langle IFE1\rangle&\to if\ condition\ then\ \langle IFE.ST\rangle\ else\ \langle IFE.ST\rangle\\ \langle IFE.ST\rangle&\to \langle ASSIGN\rangle \mid \langle IFE1\rangle\\ \langle ASSIGN\rangle &\to a:=1 \end{aligned} \]
2.32 None-Context-Free Language
对于字符集 \(\Sigma=\{1,2,3,4\}\) 上的语言 \(C=\{w\in\Sigma^*\mid w\) 中字符 \(1\) 的数量与 \(2\) 的数量相同，字符 \(3\) 的数量与字符 \(4\) 的数量相同 \(\}\)，证明语言 \(C\) 不是 Context-Free Language
Proof: 利用Pumping Lemma，考虑构造字符串 \(1^m2^m3^n4^n\) ，