0

给出下列语言的语法{0^n w 1^n | n>=0 w is in {0,1}* and |w|=n}

尝试解决方案：

S--> 0S1|R

R--> 0R|1R|empty

不确定如何保证 r 的长度与 0 或 1 的数量相同。

4

1 回答 1

2

这里什么都没有。

每个单词应该是这样的：0^nw 1^n。因此，如果我们有规则 S -> 0S1，我们会达到一个状态，我们可以从中生成的每个句子形式看起来像 0^n S 0^n。

嗯...这不是我们想要的。不是吗？

我们更进一步，我们想要一些变量 V，涉及规则 V -> 0|1（编辑：这本来是我们的“目标”，但事情可能会出错，所以我们不使用这两个规则） ，这使我们可以使用 S -> 0SV1 而不是 S-> 0S1。有什么变化？

现在我们得到这样的句子形式：0^n S (V1)^n。因此，例如 000SV1V1V1 将是一些这样的句子形式。我们现在绝对需要的一个小补充是规则 S -> empty

不过，还没有完全实现，毕竟我们希望它最终看起来更像 0^nV^n1^n。所以我们添加了一个交换 V 和 1 的规则。所以我们将 1V -> V1 添加到规则集中。现在有哪些可能？给定一个像 000SV1V1V1 这样的句子形式，我们现在可以把所有的 V 移到左边，把所有的 1 移到右边。

现在我们变成了真正的语法纳粹。我们不希望出现任何问题，因此我们进行了一些小改动。我们做了一个小小的swippidy swappidy。我们将迄今为止出现的每一个 S 都与 T 交换。所以 S -> 0SV1 变为 0TV1 等等。此外，我们添加规则 S -> empty|T 并删除规则 T -> empty。我们从中得到什么？嗯...乍一看什么都没有。但是，现在我们可以建立一种机制，确保当我们将 V 变为 1 和 0 时不会出错。

我们只需添加规则 TV -> C 和 CV -> CC。哦，耶稣基督，所有这些规则。

现在，给定一个句子形式 0^n TV^n 1^n，我们可以慢慢将其转化为 0^n C^n 1^n。什么用途？如果我们没有把所有的 V 都推到左边，什么都不会出错。所以：像 0000CCC1V111 这样的句子形式不会对我们的事业造成伤害，因为我们不能对 V 做任何事情，除非它紧挨着 C，而且，我们不可能推动 C 的周围，因为没有这样的规则。此外，由于我们要添加规则 C -> 0|1，如果我们过早地将它们更改为 1 和 0，如果仍有 V 浮动，我们将无法完成我们的任务。

这可能根本没有必要，我不确定，但这是我们证明的一部分，我们可以创建的所有单词都在我们想要用这个语法指定的单词集中。规则是：

S -> empty | T
T -> 0TV1
1V -> V1
TV -> C
CV -> CC
C -> 0|1

编辑：不过，这是一个 Type-0 Grammer。但是，通过一些更改，这可以成为等效的 CSG：

S -> empty | T
T -> 0TV1 | 0C1
1V -> V1
CV -> CC
C -> 0 | 1

主要区别在于，我们可以在某个时候决定停止将 0TV1 添加到句子形式中，而是以 0C1 结束，得到像 0^n C1 (V1) ^ (n-1) 这样的形式。同样，如果我们过早地将所有 C 转换为 0 和 1，我们将失去删除所有 V 的可能性。所以这也应该生成我们正在寻找的集合。

这也是我对 stackoverflow 上的任何事情的第一个回答，因为我有点喜欢计算机科学理论，所以我希望我的解释没有错。如果是这样，请告诉我。

于 2015-11-06T18:19:38.043 回答