1

我正在尝试用尽可能少的作品以乔姆斯基范式构造一个 CFG，它接受包含唯一字符串 a^21 的语言。

我知道我可以转换

S -> AAAAAAAAAAAAAAAAAAAAA A -> a

但是有没有其他方法可以缩短该语言然后将其转换为乔姆斯基范式？

4

1 回答 1

1

我们可以很容易地证明，我们需要至少六个符号来希望在 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 中没有语法可以生成我们的目标语言。我们通过自下而上构建语法来开始论证。

  1. 我们必须A_1 := a得到任何字符串。
  2. 我们必须A_2 := A_1 A_1得到任何长度大于 1 的字符串。
  3. 我们现在可以生成A_3或跳过它并生成A_4，或两者兼而有之。我们在下面考虑这些情况。

情况1：A_3

  1. 我们添加A_3 := A_2 A_1.
  2. 我们已经有 3 个产品，并且知道我们需要一种形式A_21 := X Y。所以我们最多可以加起来两个。即使我们添加现在可能的最大产生式 -A_6并且A_12- 我们不能A_21按要求产生（我们最多可以产生A_18 := A_6 A_12。所以添加A_3不能让我们得到一个在六个产生式中生成我们的语言的语法。

案例二：A_4

  1. 我们添加A_4 := A_2 A_2.
  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.
  3. 我们现在只有一个产品，需要它是A_20, A_19, A_17or 或A_13。我们无法使用我们现有的产品生成任何这些。

因此，我们排除了具有 6 个产生式的语法。如果您尝试使用上述推理找到具有 7 个产生式的语法，您会找到几个。由于我们知道 CNF 中有 7 个产生式的语法，而没有 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 部作品。

于 2016-04-27T13:23:15.500 回答