为乔姆斯基范式中的语言构造上下文无关文法
Construct a context free grammar for a language in Chomsky Normal Form
我正在尝试用尽可能少的产生式构建乔姆斯基范式的 CFG，它接受包含唯一字符串 a^21 的语言。
我知道我可以转换
S -> AAAAAAAAAAAAAAAAAAAAAAA
一个 -> 一个
但是有没有其他方法可以缩短该语言然后将其转换为乔姆斯基范式？
我们可以很容易地证明我们至少需要六个符号才能希望在 CNF 中为这种语言生成一个 CFG，因为我们认识到每次产生式最多可以将生成的字符串长度加倍，并且我们必须从 2^0 开始:
A_21 := ...
A_16 := A_16 A_16
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
然后我们可以证明 CNF 中没有语法，有六个产生式生成我们的目标语言。我们从自下而上构建语法开始论证。
- 我们必须
A_1 := a 才能获取任何字符串。
- 我们必须
A_2 := A_1 A_1 才能得到任何长度大于 1 的字符串。
- 我们现在可以生成
A_3 或跳过它并生成 A_4，或两者都生成。我们在下面考虑这些情况。
案例 1：A_3
- 加上
A_3 := A_2 A_1.
- 我们已经有 3 个作品，并且知道我们需要其中一个形式
A_21 := X Y。所以我们最多可以加起来两个。即使我们添加现在可能的最大产品 - A_6 和 A_12 - 我们也无法按要求生产 A_21（我们最多可以生产 A_18 := A_6 A_12。所以添加A_3 无法为我们提供在六种作品中生成我们的语言的语法。
案例 2：A_4
- 我们加上
A_4 := A_2 A_2.
- 我们已经有 3 个作品，并且知道我们需要其中一个形式
A_21 := X Y。所以我们最多可以加起来两个。我们目前的选项是 A_5、A_6 和 A_8。 A_5 和 A_6 将失败，原因与我们在上面的案例 1 中所述的相同。然而，A_8 不会因该推理而失败，因此我们添加 A_8 := A_4 A_4.
- 我们现在只有一部作品，需要它是
A_20, A_19, A_17 或 A_13。我们无法使用现有产品生成任何这些。
因此我们排除了具有 6 个产生式的文法。如果您尝试使用上述推理找到具有 7 个产生式的语法，您会找到几个。因为我们知道 CNF 中有语法有 7 个产生式和 none 有 6 个产生式，所以你已经完成了。以下是一些 7 产生式语法：
S := A_18 A_3
A_18 := A_9 A_9
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_17 A_4
A_17 := A_9 A_8
A_9 := A_8 A_1
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
S := A_16 A_5
A_16 := A_8 A_8
A_8 := A_4 A_4
A_5 := A_4 A_1
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
S := A_15 A_6
A_15 := A_9 A_6
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_14 A_7
A_14 := A_7 A_7
A_7 := A_4 A_3
A_4 := A_3 A_1
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_13 A_8
A_13 := A_8 A_5
A_8 := A_5 A_3
A_5 := A_3 A_2
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_12 A_9
A_12 := A_9 A_3
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_11 A_10
A_11 := A_10 A_1
A_10 := A_8 A_2
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
还有更多。困难的部分是显示没有 6 个作品。
我正在尝试用尽可能少的产生式构建乔姆斯基范式的 CFG，它接受包含唯一字符串 a^21 的语言。
我知道我可以转换
S -> AAAAAAAAAAAAAAAAAAAAAAA 一个 -> 一个
但是有没有其他方法可以缩短该语言然后将其转换为乔姆斯基范式？
我们可以很容易地证明我们至少需要六个符号才能希望在 CNF 中为这种语言生成一个 CFG，因为我们认识到每次产生式最多可以将生成的字符串长度加倍，并且我们必须从 2^0 开始:
A_21 := ...
A_16 := A_16 A_16
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
然后我们可以证明 CNF 中没有语法，有六个产生式生成我们的目标语言。我们从自下而上构建语法开始论证。
- 我们必须
A_1 := a才能获取任何字符串。 - 我们必须
A_2 := A_1 A_1才能得到任何长度大于 1 的字符串。 - 我们现在可以生成
A_3或跳过它并生成A_4，或两者都生成。我们在下面考虑这些情况。
案例 1：A_3
- 加上
A_3 := A_2 A_1. - 我们已经有 3 个作品，并且知道我们需要其中一个形式
A_21 := X Y。所以我们最多可以加起来两个。即使我们添加现在可能的最大产品 -A_6和A_12- 我们也无法按要求生产A_21（我们最多可以生产A_18 := A_6 A_12。所以添加A_3无法为我们提供在六种作品中生成我们的语言的语法。
案例 2：A_4
- 我们加上
A_4 := A_2 A_2. - 我们已经有 3 个作品，并且知道我们需要其中一个形式
A_21 := X Y。所以我们最多可以加起来两个。我们目前的选项是A_5、A_6和A_8。A_5和A_6将失败，原因与我们在上面的案例 1 中所述的相同。然而，A_8不会因该推理而失败，因此我们添加A_8 := A_4 A_4. - 我们现在只有一部作品，需要它是
A_20, A_19, A_17或A_13。我们无法使用现有产品生成任何这些。
因此我们排除了具有 6 个产生式的文法。如果您尝试使用上述推理找到具有 7 个产生式的语法，您会找到几个。因为我们知道 CNF 中有语法有 7 个产生式和 none 有 6 个产生式，所以你已经完成了。以下是一些 7 产生式语法：
S := A_18 A_3
A_18 := A_9 A_9
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_17 A_4
A_17 := A_9 A_8
A_9 := A_8 A_1
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
S := A_16 A_5
A_16 := A_8 A_8
A_8 := A_4 A_4
A_5 := A_4 A_1
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
S := A_15 A_6
A_15 := A_9 A_6
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_14 A_7
A_14 := A_7 A_7
A_7 := A_4 A_3
A_4 := A_3 A_1
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_13 A_8
A_13 := A_8 A_5
A_8 := A_5 A_3
A_5 := A_3 A_2
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_12 A_9
A_12 := A_9 A_3
A_9 := A_6 A_3
A_6 := A_3 A_3
A_3 := A_2 A_1
A_2 := A_1 A_1
A_1 := a
S := A_11 A_10
A_11 := A_10 A_1
A_10 := A_8 A_2
A_8 := A_4 A_4
A_4 := A_2 A_2
A_2 := A_1 A_1
A_1 := a
还有更多。困难的部分是显示没有 6 个作品。