FLA22部分作业
22 年“形式语言与自动机”课程中的部分作业整理，以我喜欢做错 / 不会做的证明题为主。
Assignment 1
Problem 7
Prove or disprove the following statement:
- Every regular language has a regular proper subset.
- \( A \), \( B \) are two languages over alphabet \( \Sigma \). If neither \( A \) or \( B \) is regular, then \( A \cup B \) is also not regular.
- If \( A \) and \( B \) are not regular languages and \( C \) is a language such that \( A \subseteq C \subseteq B \), then \( C \) is not regular.
- An infinite regular language \( L \) can be splited into two infinite disjoint, nonempty, regular subsets \( L_1, L_2 \). (Hint: use the pumping lemma.)
1. 假
考虑边界情况，如 \(L(\emptyset) = \emptyset\) ，它没有真子集。
以下结论都是正确的：
- 每个正则语言都有一个正则子集（自己）
- 每个非空正则语言都有一个正则真子集（空集）
- 能不能为每个非空正则语言找到一个正则真子集？能（见 4. ）
2. 假
举一个反例，设 \( \Sigma = \lbrace 0, 1 \rbrace, A = \lbrace 0^n1^n \mid n \in \mathbb{N} \rbrace, B = L(0^{*}1^{*}) - A \) ，\( A \) 很显然不是正则语言，而 \( L \) 很显然是正则语言，关键在于证明 \( B \) 不是正则语言。
此处可以利用 正则语言在交（差）操作下的封闭性 ，由 \( A \cup B = L \) （其实是 \(B = L - A\)）知，若 \( B \) 正则，因为 \( L \) 正则，则 \( A \) 为正则语言，与 \( A \) 非正则的性质矛盾，因此可得 \( B \) 非正则。
作业中并没有想到这一点，尝试利用了正则语言的泵引理，觉得有一点问题，但助教判定为正确，记录如下：
正则语言的泵引理
若 \( B \) 为正则语言，则存在正整数 \(n\) （称之为 \(B\) 的泵引理常数），\( \forall s \in B, |s| \geq n \) ，则 \( s \) 可拆解为 \(xyz\) 的形式 （即 \(s = xyz\)），其中 \( |xy| \leq n, |y| > 0, xy^iz \in B (i \in \lbrace 0, 1, 2, 3, \cdots \rbrace )\)
反证，假设 \( B \) 为正则语言，则有 \( B \) 对应的泵引理常数 \( n \) ，设 \( s \in B \) ，且 \( s \) 有一段长度为 \(n\) 的 \(0\) 前缀，即 \( s = 0^nw\) ，依然将 \(s\) 表示为 \(xyz\) 的形式，可设 \( y = 0^m(m > 0)\) ，则 \( xyyz = 0^{n + m}w \) ，构造 \( w = 1^{n + m} \) ，即可推出 \( xyyz \notin B\) 。
这个证明与一般的利用泵引理证明某个语言不属于正则语言的过程的最大的不同就是 \(s\) 除前缀之外的 \(w\) 部分是最后“拼凑”上去的。但从另一个角度来讲，哪怕是对于 \(0^n\) ，也足以应用泵引理，也就是说 \(m\) 的大小确定，所以在这里姑且认为 \(w\) 是确定存在且能被确定构造出来的 。
解析里给了一个巧妙的构造：设 \( A = \lbrace 0^m1^n \mid m \geq n, m, n \in \mathbb{N} \rbrace, B = \lbrace 0^m1^n \mid m \leq n, m, n \in \mathbb{N} \rbrace, A \cup B = L(0^{*}1^{*})\) 。
3. 假
考虑 \( \Sigma = \lbrace 0, 1, a, b \rbrace, A = \lbrace 0^n1^n \mid n \in \mathbb{N} \rbrace, C = \lbrace 0^m1^n \mid m, n \in \mathbb{N} \rbrace , B = \lbrace 0^m1^na^pb^p \mid m, n, p \in \mathbb{N} \rbrace \) ，很显然 \( A \subseteq C \subseteq B \) ，\( A \) 不是正则语言，\( C \) 是正则语言，关键在于证明 \( B \) 不是正则语言（看上去就不是正则语言 qaq ）。
比较简便的做法是利用正则语言在同态下的封闭性，设同态函数 \(h, h(0) = \epsilon, h(1) = \epsilon, h(a) = 0, h(b) = 1\) ，则 \(h(B) = A\) （虽然在这里不重要但是这个写法对吗？），若 \( B \) 正则，则 \( A \) 必定正则，矛盾。所以 \(B\) 不是正则语言。
4. 真
根据提示，考虑使用泵引理，可在 \( L \) 中任取 \(w (|w| \geq n)\) ，设 \(w = xyz\) ，由 \( xy^iz \in B \) 可以猜测出将两部分串按照 \(i\) 奇偶性分类。
在作业中，我取了 \( L_1 = \lbrace xy^{2i}z \mid i \in \mathbb{N}, i \geq 1 \rbrace \) ，又对称地取了 \( L_2 = \lbrace xy^{2i + 1}z \mid i \in \mathbb{N} \rbrace \)，这里应该是没想清楚，因为 \( L_1 \cup L_2 \neq L \) 。
事实上，只需取 \( L_1 = \lbrace xy^{2i}z \mid i \in \mathbb{N} \rbrace \) ，然后取 \(L_2 = L - L_1\) 即可。由正则语言在集合差操作下的封闭性可知，若能证明 \(L_1\) 是正则语言，则 \(L_2\) 也是正则语言。在作业中，我只是感觉 \(L_1\) 是正则语言非常显然，并没有证明，这里应当需要补充一个简单的证明。事实上可以使用正则表达式，\( L_1 = L(x(yy)*z) \) 。
现在可以回过头来看看 1. 中最后提出的那个问题：对于正则语言 \(L\) ，若 \(|L| > 1\) ，则能否为 \(L\) 找到一个正则真子集？
按照 \(L\) 是有限还是无限集讨论：
- 若 \(L\) 有限，则可按照字典序将 \(L\) 中的串排序，删去最后一个即可。
- 若 \(L\) 无限，直接使用上面的构造方式。
Problem 8(Bonus)
- For a language \(L\), let \(A(L)\) be the language \(\lbrace wv \mid \exist v \in \Sigma. vw \in L \rbrace\). Show that if \(L\) is regular, so is \(A(L)\).
- For a language \(L\), let \(B(L)\) be the language \(\lbrace wv \mid \exist v \in Sigma^{*}. vw \in L \rbrace\). Show that if \(L\) is regular, so is \(B(L)\).
所以搞了半天似乎 Bonus 是没有加分的，意思是你做了题目自己获得了提升。笑死了，不过 Bonus 应该就没有做出来过。
这道题的核心思想是利用 \(L\) 对应的 DFA 构造 \(\epsilon\)NFA，具体的细节以后有机会再详细写吧。
犯的一个错误是 2. 不能利用 1. 的结论（属于是初高中数学思维定式了），一个错解是这样的：
- \( \forall i \in \mathbb{N}, B_i(L) = \lbrace wv \mid \exist v \in \Sigma^{i}. vw \in L \rbrace \)
- \( B_0(L) = L, B_1(L) = A(L), B_2(L) = A(B_i(L)), \forall i \in N, B_i(N) \in \text{RE by induction} \)
- \(B(L) = \bigcup_{i = 0}^{\infty} B_i(L) \in \text{RE(closed under union)} \)
看上去很对，但是问题出在最后一步，正则语言在有限交下封闭，但是在无限交下不一定封闭，考虑一个反例：
- \(L_i = \lbrace 0^i1^i \rbrace, \forall i \in \mathbb{N}, L_i \in \text{RE}\)
- \(L = \bigcup_{i = 0}^{\infty} L_i = \lbrace 0^n1^n \mid n \in \mathbb{N} \rbrace \notin \text{RE}\)
Assignment 2
Problem 7
For any contest-free language \(L\) and any regular language \(R\), answer each of the following statements True or False. If your answer is True, give an explanation. If your answer is False, give a counterexample.
- \(L - R\) is context-free.
- \(R - L\) is context-free.
- \(S(L) = \lbrace w \mid \exist v \in \Sigma^{*}. vw \in L\rbrace \) . \(S(L)\) is context-free.
- (Bonus) \(H(L) = \lbrace w \mid \exist v \in \Sigma^{*}. vw \in L \land |v| = |w| \rbrace\). \(H(L)\) is context-free. (Hint: intersection with a regular language.)
1. True && 2. False
\(L - R = L \cap \overline{R}\) 。这里的 \(\overline{R}\) 其实是针对语言的全集 \(\Sigma^{*}\) 来说的，全集是一个正则语言，由正则语言在差操作下的封闭性知 \(\overline{R}\) 也是一个正则语言；又由上下文无关语言与正则语言在交操作下的封闭性知 \(L \cap \overline{R}\) 也是一个上下文无关语言。
相似地，\( R - L = R \cap \overline{L}\) 。但上下文无关语言在集合差操作下不封闭，即 \(\overline{L}\) 不一定是上下文无关语言。这里需要一个反例。考虑构造一个 \(L(a^nb^nc^n)\) 的典型的非上下文无关语言，可设 \(R = L(a^{*}b^{*}c^{*}), L = \lbrace a^ib^jc^k \mid i \neq j \lor j \neq k \rbrace\) ，关键在于证明 \(L\) 是上下文无关语言。
可以将 \(L\) 拆解为 \(L_1 \cup L_2\) ，其中 \(L_1 = \lbrace a^ib^jc^k \mid i \neq j \rbrace, L_2 = \lbrace a^ib^jc^k \mid j \neq k \rbrace \)，由上下文无关语言在并操作下的封闭性可知 \(L\) 也是上下文无关语言。
有一个典型的错解是构造 \(L\) 和 \(R\) 的并行 PDA（PDA in parallel），然后标记 \(L\) 和 \(R\) 对应的结束状态，如在 1. 中将 \([p, q] (p \in F(L), q \notin F(R))\) 标记为接受状态。这样的做法在 1. 中是没问题的，但是在 2. 中不成立。
对于确定性的自动机，将所有的接受状态和非接受状态取反，得到的新自动机接受原语言的补集，但是这一点对于非确定性的自动机是不成立的。反例似乎遍地都是，比如我随手写了一个 \(L(ab^{*} + c^{*})\)。所以 \(\overline{L}\) 的自动机不能很好地构造出来。
3. True
构造一：构造上下文无关文法
Chomsky 范式
一个文法满足 Chomsky 范式，当且仅当所有产生式都满足以下三者之一。
- \( A \to BC \)
- \( A \to a \)
- \( S \to \epsilon \)
对于 \(L\) 的一个满足 Chomsky 范式的 CFG \(G = (V, T, P, S)\) ，构造一个新的 CFG \(G’ = (V’, T, P’, S’)\) 使 \(L(G’) = S(G)\)。
- \(V’ = V \cup {A’ \mid A \in V}\) ，即将所有的非终结符都复制一份。
- For each \(A \to a \in P\), add\(A \to a, A’ \to \epsilon | a\) to P’.
- For each \(A \to BC \in P\), add \(A \to BC, A’ \to B’C | C’\) to P’.
对于 \(G’\) ，从 \(S’\) 开始推导，\(A’\) 会忽略前缀，而 \(A\) 则会保留所有的后缀，因此 \(L(G’)\) 中含有 \(L\) 中所有的后缀。
构造二：构造 PDA
可以将状态 \(Q\) 复制两份 \(Q_0, Q_1\) ，其中 \(Q_0\) 的所有转移都使用 \(\epsilon\)，用来忽略前缀 ，而 \(Q_1\) 的所有转移都保持不变，用来忽略后缀。\(Q_0\) 和 \(Q_1\) 的栈上的转移保持不变。并在 \(Q_0\) 和 \(Q_1\) 之间对应的节点使用 \(\epsilon\) 边连起来，表示从忽略前缀到处理后缀的过程。
这个新的 PDA 其实是一个分层图，只能从 \(Q_0\) 所在的层“向上”走到 \(Q_1\) 所在的层，同时能够保留所有的栈状态以确保能够顺利接受。因此新 PDA 可以接受 \(S(L)\) 。
4. False
构造反例，设 \(L = \lbrace a^{3n}b^{n}c^{m}d^{m} \mid m, n \in \mathbb{N} \rbrace\) ，考虑 \(L’ = H(L) \cap R\) ，其中 \(R = L(b^{+}c^{*}d^{*})\) ，则 \(L’ = \lbrace b^{p}c^{m}d^{m} \mid 0 < p \leq m \rbrace\) 。
因为 \(L\) 是由两个上下文无关语言连接而成的，所以 \(L\) 也是上下文无关语言。在 \(L’\) 中 \(0 < p \leq m\) 的限制中，\(0 < p\) 来源于 \(b^{+}\) ，而 \(p \leq m\) 则是来源于正则表达式中不包含 \(a\) 的要求，若 \(p > m\) ，则 \(H(L)\) 中一定包含 \(a\) ，与 \(R\) 交完之后不可能出现这种串。
那么这个 \(L’\) 里面有两个限制，看上去就不是上下文无关语言，又根据上下文无关语言和正则语言的交是上下文无关语言，若 \(H(L)\) 是上下文无关语言，则 \(H(L) \cap R\) 也一定是上下文无关语言。若能证明 \(L’\) 不是上下文无关语言，则 \(H(L)\) 就不是上下文无关语言，反例构造成立。
可以使用上下文无关语言的泵引理很方便地证明。
上下文无关语言的泵引理
若 \(L\) 为上下文无关语言，则存在泵引理常数 \(n\) ，\(\forall z \in L, |z| \geq n\) ，可以将 \(z\) 拆分为 \(uvwxy\) ，即 \(z = uvwxy\) ，其中 \(|vwx| \leq n, |vx| \geq 1\) ，\(\forall k \in \lbrace 0, 1, 2, \ldots \rbrace\)， \(uv^{k}wx^{k}y \in L\) 。
在做题的过程中，发现了一件比较有意思看上去也比较有用的事情，就是在泵引理的应用过程中，可以不妨设 \(|u| < n \)。因为若 \(|u| \geq n\) ，可以直接对 \(u\) （不断）应用泵引理直到 \(|u| < n\) 。
那么对于 \(L’\) ，可以直接取 \(z = b^{2n}c^{2n}d^{2n} = uvwxy \) ，不妨设 \(|u| < n\)，那么 \(v, x\) 都是一段 \(b\) ，设 \(|vx| = l\) ，取 \(k = n\)，则 \(uv^kwx^ky = b^{2n + ln}c^{2n}d^{2n} \notin L’\) ，因此 \(L’\) 不是上下文无关语言。