Class Notes on 10th Oct

语言非正则性证明

引理 设 $\Sigma$ 为字母表，$A \subseteq \Sigma^\ast$ 为正则语言，则存在 n 满足：$\forall w \in A$，当 $|w|\geq n$ 时，有

$w=xyz,x,y,z \in \Sigma^\ast$

• $y \neq \epsilon$
• $|xy| \leq n$
• $x y^i z \in A,i=0,1,2,\cdots$

证明 设 $A$ 被 DFA $M=(Q,\Sigma,\delta,q_0,F)$ 识别，且 $|Q|=n$，既然 $w \in A$，有以下转移 $\delta(r_i,a_{i+1})=r_{i+1}$，其中 $w=a_1 a_2 \cdots a_m(m \geq n)$，$r_i \in Q,i=0,1,2,\cdots$，$r_0=q_0$，$r_m \in F_0$。【？】

由于 $|Q| = n \leq m$，所以 $r_0,\cdots,r_m$ 中必定有两个状态相同，记为 $r_s,r_t,0 \leq s < t \leq t$。

若取 $x=a_1 \cdots a_s,y=a_{s+1} \cdots a_{t},z=a_{t+1} \cdots a_m$，则定理中的条件必定满足。$\blacksquare$

Problem 1 设 $\Sigma = \{0, 1\}$，$L_{same} = \{0^m 1^m:m \in N\}$，证明其为非正则语言。

证明 （反证法）若 $L_{same}$ 是正则的，则存在 $n \geq 1$ 满足泵引理，考虑 $w=0^n 1^n$，则有 $w=xyz$，其中 $y \neq \epsilon$，且 $|xy| \leq n$，以及 $x y^i z \in L_{same},i=0,1,2,\cdots$。 另 $y = 0^k(k \geq 1),x = 0^{k_1},z = 0^{k_2} 1^n$。

显然当 $i \neq 1$ 时，$x y^i z \not\in L_{same}$，这是矛盾的，因此是 $L_{same}$ 非正则的。

Problem 2 $\Sigma = \{ 0, 1 \},A = \{ 0^m 1^r : m, r \in N, m > r\}$，证明其是非正则的。

证明 （反证法）设 $A$ 是正则的，则存在 $n$ 满足泵原理。取 $w = 0^{n+1} 1^n \in A$，有 $w = xyz$ 满足

• $y \neq \epsilon$
• $|xy| \leq n$
• $x y^i z \in A,i=0,1,2,\cdots$

其中 $y = 0^k (k \geq 1)$，然而 $xz = 0^{n+1-k} 1^n \not\in A$，因此 $A$ 非正则。$\blacksquare$

Problem 3 $\Sigma = \{ 0 \}$，$L_{square} = \{ 0^{m^2} : m \in N\}$，证明其是非正则的。

证明 （反证法）若 $L_{square}$ 是正则的，则存在 $n$ 满足泵引理。取 $w = 0^{n^2} \in L_{square}$，有 $w = xyz$ 满足

• $y = 0^k(k \geq 1)$
• $|xy| \leq n$
• $x y^i z \in A,i=0,1,2,\cdots$

当 $i = 2$ 时，由于 $n^2 + 1 \leq n^2 + k \leq n^2 + n$，所以 $n^2 + k$ 不是完全平方数，因此 $x y^2 z \not\in L_{square}$。$\blacksquare$

作业 证明 $L_{pal} = \{ w \in \Sigma^\ast : w = w^R \}$ 是非正则的，其中 $\Sigma = \{ 0, 1 \}$，$w^R$ 是 $w$ 的反转，如 $w = a_1 a_2 \cdots a_m$，则 $w^R = a_m a_{m-1} \cdots a_1$。

证明 假设 $L_{pal}$ 是正则语言。根据正则语言的泵引理，存在一个整数 $n$（称为泵长度），使得对于所有 $w \in L_{pal}$ 且 $|w| \geq n$ 的字符串 $w$，我们可以将其分解为 $w = xyz$，并且满足以下条件：

• $|xy| \leq n$，
• $|y| > 0$，
• 对于所有 $i \geq 0$，$xy^i z \in L_{pal}$（即泵出的字符串仍然在语言中）。

取 $w = 0^n 1 0^n$，这是一个长度为 $2n + 1$ 的回文字符串，显然 $w \in L_{pal}$，且 $|w| = 2n + 1 \geq n$。

根据泵引理，字符串 $w$ 可以分解为 $w = xyz$，并且满足：

1. $|xy| \leq n$，
2. $|y| > 0$。

由于 $|xy| \leq n$，可以得出 $x$ 和 $y$ 都仅包含字符 0，因此 $y = 0^k$，其中 $k > 0$。

现在我们考虑 $i = 2$ 的情况。此时，泵出的字符串为：

$$w' = xy^2z = 0^{n+k} 1 0^n$$

这是一个新的字符串，前缀为 $0^{n+k}$，后缀为 $0^n$。

显然，$w'$ 不是回文字符串，因为前缀和后缀的长度不同。具体地，前缀包含 $n + k$ 个 0，而后缀只包含 $n$ 个 0，因此 $w' \neq w'^R$，即 $w' \notin L_{pal}$。

根据泵引理的条件，所有泵出的字符串 $xy^i z$ 都应属于语言 $L_{pal}$。但是，我们已经证明当 $i = 2$ 时，$w' \notin L_{pal}$。这与泵引理的结论矛盾。

因此，语言 $L_{pal}$ 不是正则语言。

正则语言的进一步讨论

对于 $w \in \Sigma^\ast$，$w^R$ 定义为

• 若 $w = \epsilon$，则 $w^R = \epsilon$
• 若 $w = a x, (a \in \Sigma, x \in \Sigma^\ast)$，则 $w^R = x^R a$
• $A \in \Sigma^\ast$，$A^R = \{ w^R: w \in A \}$
• $(A \cup B)^R = A^R \cup B^R$
• $(AB)^R = B^R A^R$
• $(A^\ast)^R = (A^R)^\ast$

Question 若 A 是正则的，$A^R$ 是否为正则的？

命题 若 $A \subseteq \Sigma^\ast$ 是正则的，则 $A^R$ 也是正则的。

证明

（方法1） 如果 S 是正则表达式，则其反转也可用递归定义：

• $S = \varnothing \rightarrow S^R = \varnothing$
• $S = \epsilon \rightarrow S^R = \epsilon$
• $S = a, a \in \Sigma, S^R = a$
• $S = S_1 \cup S_2$，$S_1, S_2$ 其中为正则表达式，$S^R = S_1^R \cup S_2^R$
  • $S = (S_1 S_2) \rightarrow S^R = (S_2^R, S_1^R)$
  • $S = (S_1^\ast) \rightarrow \left(\left(S_1^R\right)^\ast\right)$

可见正则表达式的反转也是正则表达式，且 $L(S^R) = L(S)^R$，其中 $S$ 为正则表达式。

something need to fill

对称差

$A \triangle B = (A \backslash B) \cup (B \backslash A)$

$A \triangle B = (A \cap \overline B) \cup (\overline A \cap B)$

前缀、后缀和子串

设 $A \subseteq \Sigma^\ast$，则

• $\text{Prefix}(A) = \{ x \in \Sigma^\ast : \exists v \in \Sigma^\ast, xv \in A \}$
• $\text{Suffix}(A) = \{ x \in \Sigma^\ast : \exists v \in \Sigma^\ast, vx \in A \}$
• $\text{Substring}(A) = \{ x \in \Sigma^\ast : \exists u, v \in \Sigma^\ast, uxv \in A \}$

命题 若 $A \subseteq \Sigma^\ast$ 为正则语言，则上述三个均为正则语言。

证明 设 DFA $M=(Q, \Sigma, \delta, q_0, F)$ 识别 $A$，记

$$R = \{ q \in Q : \exists w \in \Sigma^\ast, \delta(q_0, w) = q \}$$ $$P = \{ p \in Q : \exists w \in \Sigma^\ast, \delta(p, w) \in F \}$$

构造 DFA $K = (Q, \Sigma, \delta, q_0, P)$，则 $L(K) = \text{Prefix}(A)$

NFA $N = (Q \cup \{ r_0 \}, \Sigma, \eta, r_0, F), \eta(r_0, \epsilon) = R, \eta(q, a) = \{ \delta(q, a) \}, q \in Q, a \in$