10.1. 引言¶

下面给出另外两个（略显奇特的）对正则语言封闭的性质。

10.2. 性质与证明：问题 1¶

考虑性质 Replace_one_a_with_b，简记为 R1awb。 如果 \(L\) 是正则的，证明 R1awb(\(L\)) 是正则的。

对语言 \(L\) 应用性质 R1awb，会把每个串中的一个 \(a\) 替换为一个 \(b\)。 如果一个串不含 \(a\)，那么该串不属于 R1awb(\(L\))。

这意味着什么？我们想证明什么？

示例 1 ：考虑 \(L = \{aaab, bbaa\}\)

\(L\) 是正则的吗？是的，你可以应用该性质。

\(\mathrm{R1awb}(L) = \{baab, abab, aabb, bbba, bbab\}\)

示例 2 ：考虑 \(\Sigma=\{a, b\}\)， \(L = \{w \in \Sigma^{*} \mid w \mathrm{\ has\ an\ even\ number\ of\ } a's \mathrm{\ and\ an\ even\ number\ of\ } b's \}\)

\(L\) 是正则的吗？是的，你怎么知道的？ 我们为这个语言构造了一个 DFA。

\(\mathrm{R1awb}(L) = \{w \in \Sigma^{*} \mid w \mathrm{\ has\ an\ odd\ number\ of\ } a's \mathrm{\ and\ an\ odd\ number\ of\ } b's\}\)

证明：

10.3. 性质与证明——问题 2¶

考虑性质 Truncate_all_preceeding_b's（删除所有前导的 b），简记为 TruncPreb。 如果 \(L\) 是正则的，证明 TruncPreb(\(L\)) 是正则的。

对语言 \(L\) 应用性质 TruncPreb，会删除每个串中所有前导的 b。 如果一个串没有前导的 b，那么该串在 TruncPreb(\(L\)) 中保持不变。

这意味着什么？我们想证明什么？

示例 1 ：考虑 \(L = \{aaab, bbaa\}\)

\(L\) 是正则的吗？是的，你可以应用该性质。

\(\mathrm{TruncPreb}(L) = \{aaab, aa\}\)

示例 2 ：考虑 \(L = \{(bba)^n \mid n > 0\}\)

\(L\) 是正则的吗？是的。 你怎么知道的？我们为这个语言构造了一个 DFA。

\(\mathrm{TruncPreb}(L)= \{a(bba)^n \mid n \ge 0\}\)

证明：

复制一份 DFA。 对于第一份中的每条 a 弧，把它删除，改为让 \(a\) 弧指向 下方对应的目的状态。

对于第一份中的每条 \(b\) 弧，把 \(b\) 改为 lambda。