context-free-grammar - 如何快速转换为乔姆斯基范式？

Question

所以我知道基本的 4 步方法。删除 epsilon，然后是小于 2 的变量，依此类推。但是，对于我们在测试中必须做的问题，这种方式花费的时间太长了。

这是一个示例：
将此上下文无关文法转换为等效的乔姆斯基范式文法。请记住从语法中删除所有无用的符号。

这是考试 6 个问题中的 1 个。我们有 50 分钟的时间来完成整个测试。我可以做到这一点，但每次大约需要 30-40 分钟。有没有人知道任何技巧或捷径可以让这样的事情变得更快？

谢谢。

score 3 · Accepted Answer

您可以使用一些策略来减少获得答案的时间。首先，您可能会尝试直接理解语法的语言，而不是转换给定的语法，而是在 CNF 中为相同的语言写下新的语法。我不知道这对于给出的示例特别有用，但它可能很有用，特别是如果 - 在测试中 - 您将语法识别为对应于已知语言，或者如果该语言被命名或以其他方式描述。

否则，我会在尝试删除 ε 之前寻找简化语法的方法。这一步增加了你的语法规模，你希望尽可能晚地完成，以避免之前不得不考虑更大的语法。在这个例子中，这有一些不平凡的回报。

首先，查看每个符号是否导致语言中的字符串。这应该很快。消除任何没有用的符号，因为它们甚至没有潜在的用处。

对于您的语法：

这已经让我们受益匪浅。考虑新语法：

S → TaXU
T → UU | abc 
U → bSc | ε 
X → bT | Tc 
Y → cba | ε

接下来，查找除 S 之外未出现在剩余产生式中的任何非终结符。我们可以很快看到在这个新语法Y中无法访问S它，并且可以将其删除以获得：

S → TaXU
T → UU | abc 
U → bSc | ε 
X → bT | Tc

可能可以重复上述步骤以继续删除无用的非终结符号和产生式。我认为剩下的一切都是有用的。

现在我们可以消除了ε。执行此操作的标准方法是添加用于ε代替U. 我们有两个使用 U 的产品和三个要添加的新产品。我们的新语法如下所示：

S → TaXU | TaX
T → UU | U | abc | ε 
U → bSc
X → bT | Tc

重复T：

S → TaXU | aXU | TaX | aX
T → UU | U | abc
U → bSc
X → bT | Tc | b | c

我们只有一个产生式将一个非终结符带到另一个，我们可以通过替换来消除它：

S → TaXU | aXU | TaX | aX
T → UU | bSc | abc
U → bSc
X → bT | Tc | b | c

现在，剩下的不应该花太长时间——我们已经过了最困难的部分，即消除空产生式和派生单个非终结符的产生式。现在，我们只需要介绍终结符以及终结符和非终结符字符串的产生式。我建议您从较短的字符串开始，然后逐步提高。

我们看到一些终结符号出现在非终结符旁边，这是不可能的，所以你总是可以为它们添加新的非终结符：

S → TAXU | AXU | TAX | AX
T → UU | BSC | ABC
U → BSC
X → BT | TC | b | c
A → a
B → b
C → c

现在，从最短的字符串（长度 > 2）开始，添加一次派生两个的新符号。为了节省时间，只需从左到右工作。我们看到BSC, ABC,TAX和AXU。TAXU我们可以添加G → BS, H -> AB, I → TA,J → XU并得到：

S → IJ | AJ | IX | AX
T → UU | GC | HC
U → GC
G → BS
H → AB
I → TA
J → XU
X → BT | TC | b | c
A → a
B → b
C → c

现在，这是否需要 8 分钟才能在测试情况下完成问题（6 个问题，50 分钟）？这有点紧。我确实花了更长的时间来输入解释。划掉符号和产生式应该很快，但添加产生式意味着把它们写下来，这需要一些时间。

1 回答 1