如何快速转换为乔姆斯基范式？
How to convert to Chomsky Normal Form quickly?
所以我知道基本的 4 步方法。删除 epsilons，然后是小于 2 的变量，依此类推。但是，对于我们在测试中必须做的问题，这种方法花费的时间太长了。
这是一个例子：
将此上下文无关文法转换为等效的 Chomsky 范式文法。
请记住从语法中删除所有无用的符号。
S → TaXU | STUVWXY
T→UU |美国广播公司
U → 理学士 | ε
V → AV |白
W → 顺时针 | Va
X → bT | TC
Y→CBA | ε
这是测试的 6 道题中的第 1 道。我们有 50 分钟的时间来完成整个测试。我可以做这个，但每次要花 30-40 分钟。有谁知道任何技巧或捷径可以使这样的事情变得更快？
谢谢。
您可以使用一些策略来减少获得答案的时间。首先，您可能会尝试直接理解语法的语言，而不是转换给定的语法，而是在 CNF 中为相同的语言写下新的语法。我不知道这对于给定的示例特别有用，但它可能有用，特别是如果 - 在测试中 - 您将语法识别为与已知语言相对应，或者如果语言被命名或以其他方式描述。
否则，我会在尝试删除 ε 之前寻找简化语法的方法。该步骤会增加语法的大小，并且您希望尽可能晚地完成该步骤，以避免不得不更早地考虑更大的语法。这在这个例子中有一些不平凡的回报。
首先，看看每个符号是否都指向该语言中的一个字符串。这应该很快。消除任何没有的符号，因为它们甚至没有潜在用处。
- 如果一个非终结符指向一串终结符，它可能很有用。
- 如果一个非终结符导致一串终结符和可能有用的非终结符，则它可能有用。
语法方面：
Y -> cba 所以 Y 可能有用X -> bT -> babc 所以 T 可能有用W 和 V 不会导致任何有用的地方；他们只派生字符串，包括他们自己或彼此，而且没有一个被证明是潜在有用的。这些符号，和任何包含它们的产品，可以立即被丢弃。U -> e 所以 U 可能有用。T -> abc 所以 T 可能有用S -> TaXU -> abcaXU -> abcabTU -> abcababcU -> abcababc 所以 S 可能有用（太糟糕了！）
这已经让我们收获颇丰。考虑新语法：
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 分钟）吗？这有点紧。我肯定花了更长的时间来输入解释。划掉符号和产生式应该很快，但是添加产生式意味着将它们写下来，这需要一些时间。
所以我知道基本的 4 步方法。删除 epsilons，然后是小于 2 的变量，依此类推。但是，对于我们在测试中必须做的问题，这种方法花费的时间太长了。
这是一个例子：
将此上下文无关文法转换为等效的 Chomsky 范式文法。
请记住从语法中删除所有无用的符号。
S → TaXU | STUVWXY
T→UU |美国广播公司
U → 理学士 | ε
V → AV |白
W → 顺时针 | Va
X → bT | TC
Y→CBA | ε
这是测试的 6 道题中的第 1 道。我们有 50 分钟的时间来完成整个测试。我可以做这个，但每次要花 30-40 分钟。有谁知道任何技巧或捷径可以使这样的事情变得更快？
谢谢。
您可以使用一些策略来减少获得答案的时间。首先，您可能会尝试直接理解语法的语言，而不是转换给定的语法，而是在 CNF 中为相同的语言写下新的语法。我不知道这对于给定的示例特别有用，但它可能有用，特别是如果 - 在测试中 - 您将语法识别为与已知语言相对应，或者如果语言被命名或以其他方式描述。
否则，我会在尝试删除 ε 之前寻找简化语法的方法。该步骤会增加语法的大小，并且您希望尽可能晚地完成该步骤，以避免不得不更早地考虑更大的语法。这在这个例子中有一些不平凡的回报。
首先，看看每个符号是否都指向该语言中的一个字符串。这应该很快。消除任何没有的符号，因为它们甚至没有潜在用处。
- 如果一个非终结符指向一串终结符，它可能很有用。
- 如果一个非终结符导致一串终结符和可能有用的非终结符，则它可能有用。
语法方面：
Y -> cba所以Y可能有用X -> bT -> babc所以T可能有用W和V不会导致任何有用的地方；他们只派生字符串，包括他们自己或彼此，而且没有一个被证明是潜在有用的。这些符号，和任何包含它们的产品，可以立即被丢弃。U -> e所以U可能有用。T -> abc所以T可能有用S -> TaXU -> abcaXU -> abcabTU -> abcababcU -> abcababc所以S可能有用（太糟糕了！）
这已经让我们收获颇丰。考虑新语法：
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 分钟）吗？这有点紧。我肯定花了更长的时间来输入解释。划掉符号和产生式应该很快，但是添加产生式意味着将它们写下来，这需要一些时间。