龙书习题4.2.3 f：两半不同的字符串的文法
Dragon book exercise 4.2.3 f: Grammar for strings whose two halfs differ
我可以自己解决4.2.3 a~e，但是f对我来说太难了，我什至用google都找不到答案。
Design grammars for the following languages:
(f) The set of all strings of 0s and 1s of the form xy, where x ≠ y and x and y are of the same length
这种语言的有趣之处在于它与
的关系
L<sub>dup</sub> = { ωω | ω∈ Σ<sup>*</sup>}
这是非上下文无关语言的典型例子。但是练习中的语言
L<sub>diff</sub> = { γζ | γ ≠ ζ ∧ γ ∈ Σ<sup>*</sup> ∧ ζ ∈ Σ<sup>*</sup>}
有 属性
L<sub>diff</sub> ⋃ L<sub>dup</sub> ⋃ L<sub>奇数</sub> = Σ<sup>*</sup> 和 L<sub>dup</sub>, L<sub>diff</sub>, L<sub>odd</sub> 是不相交的。
哪里
L<sub>奇数</sub> = { ω | |ω|是奇数 ∧ ω ∈ Σ<sup>*</sup>}
换句话说，如果你把一个字符串分成两个等长的部分，这两个部分要么相等，要么不等，如果你不能那样分割字符串，它的长度就是奇数。
Lodd 显然是上下文无关的——事实上，它是规则的——所以 Ldiff 是上下文的事实free 得出的结论是上下文无关语言的补语可能不是上下文无关的。
鉴于此，很自然地认为 Ldiff 是由两个等长的片段 γ 和 ζ。但这以一种使问题难以解决（如果不是不可能的话）的方式来界定问题。与许多数学问题（我敢说，现实世界的问题）一样，解决方案必须从重构问题开始，以揭示其潜在的简单性。 （"Thinking outside of the box"，套用著名的陈词滥调。）
假设γ和ζ的长度都是n。既然不同，那么至少在一个位置上肯定是不同的。假设k是这样一个位置，使得γk≠ζ k.
现在，让我们尝试描述满足该约束的字符串对的特征。除了位置 k 之外的所有符号都是无关紧要的，所以我们最终得到的是：
Σ<sup>k</sup>γ<sub>k</sub>Σ<sup>n-k-1</sup>Σ<sup>k</sup>ζ<sub>k</sub>Σ<sup>n-k-1</sup>
这显然与
相同
Σ<sup>k</sup>γ<sub>k</sub>Σ<sup>k</sup>Σ<sup>n-k-1</sup>ζ<sub>k</sub>Σ<sup>n-k-1</sup>
并让j等于; n−k−1, a = γk 和 b = ζk，我们得到
Σ<sup>k</sup>aΣ<sup>k</sup>Σ<sup>j</sup>bΣ<sup>j</sup>,a≠b
j 和 k 以及两个符号 a 和 b 在那个表达式中都是任意的。所以实际上，我们已经描述了一组字符串，它可以被分成两个奇数长度的部分，使得两个部分中间的符号不同。对于二进制字符串，只有两对不同的符号：<0, 1> 和 <1, 0>。所以这导致了以下语法：
W → 0 | 1 /* Wildcard */
A → 0 | W A W /* Strings with a 0 in the middle */
B → 1 | W B W /* Strings with a 1 in the middle */
S → A B | B A /* L<sub>diff</sub> */
我可以自己解决4.2.3 a~e，但是f对我来说太难了，我什至用google都找不到答案。
Design grammars for the following languages:
(f) The set of all strings of 0s and 1s of the form xy, where x ≠ y and x and y are of the same length
这种语言的有趣之处在于它与
的关系L<sub>dup</sub> = { ωω | ω∈ Σ<sup>*</sup>}
这是非上下文无关语言的典型例子。但是练习中的语言
L<sub>diff</sub> = { γζ | γ ≠ ζ ∧ γ ∈ Σ<sup>*</sup> ∧ ζ ∈ Σ<sup>*</sup>}
有 属性
L<sub>diff</sub> ⋃ L<sub>dup</sub> ⋃ L<sub>奇数</sub> = Σ<sup>*</sup> 和 L<sub>dup</sub>, L<sub>diff</sub>, L<sub>odd</sub> 是不相交的。
哪里
L<sub>奇数</sub> = { ω | |ω|是奇数 ∧ ω ∈ Σ<sup>*</sup>}
换句话说，如果你把一个字符串分成两个等长的部分，这两个部分要么相等，要么不等，如果你不能那样分割字符串，它的长度就是奇数。
Lodd 显然是上下文无关的——事实上，它是规则的——所以 Ldiff 是上下文的事实free 得出的结论是上下文无关语言的补语可能不是上下文无关的。
鉴于此，很自然地认为 Ldiff 是由两个等长的片段 γ 和 ζ。但这以一种使问题难以解决（如果不是不可能的话）的方式来界定问题。与许多数学问题（我敢说，现实世界的问题）一样，解决方案必须从重构问题开始，以揭示其潜在的简单性。 （"Thinking outside of the box"，套用著名的陈词滥调。）
假设γ和ζ的长度都是n。既然不同，那么至少在一个位置上肯定是不同的。假设k是这样一个位置，使得γk≠ζ k.
现在，让我们尝试描述满足该约束的字符串对的特征。除了位置 k 之外的所有符号都是无关紧要的，所以我们最终得到的是：
Σ<sup>k</sup>γ<sub>k</sub>Σ<sup>n-k-1</sup>Σ<sup>k</sup>ζ<sub>k</sub>Σ<sup>n-k-1</sup>
这显然与
相同Σ<sup>k</sup>γ<sub>k</sub>Σ<sup>k</sup>Σ<sup>n-k-1</sup>ζ<sub>k</sub>Σ<sup>n-k-1</sup>
并让j等于; n−k−1, a = γk 和 b = ζk，我们得到
Σ<sup>k</sup>aΣ<sup>k</sup>Σ<sup>j</sup>bΣ<sup>j</sup>,a≠b
j 和 k 以及两个符号 a 和 b 在那个表达式中都是任意的。所以实际上，我们已经描述了一组字符串，它可以被分成两个奇数长度的部分，使得两个部分中间的符号不同。对于二进制字符串，只有两对不同的符号：<0, 1> 和 <1, 0>。所以这导致了以下语法：
W → 0 | 1 /* Wildcard */
A → 0 | W A W /* Strings with a 0 in the middle */
B → 1 | W B W /* Strings with a 1 in the middle */
S → A B | B A /* L<sub>diff</sub> */