将语法转换为Chomsky范式？ [英] Converting grammar to Chomsky Normal Form?

问题描述

将下面的语法转换为Chomsky Normal Form。给出所有中间步骤。

Convert the grammar below into Chomsky Normal Form. Give all the intermediate steps.

S -> AB | aB
A -> aab|lambda
B -> bbA

好，所以我要做的第一件事就是添加一个新的起始变量 S0

Ok so the first thing I did was add a new start variable S0

所以现在我有

S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA

然后我删除了所有的lambda规则：

then I removed all of the lambda rules:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

然后我检查了 S-> S 和 A-> B 类型规则不存在。那就是我想出的答案，我需要做进一步的事情还是做错什么事情？

Then I checked for S->S and A->B type rules which did not exist. And that was the answer I came up with, do I need to do anything further or did I do anything wrong?

推荐答案

Wikipedia说：

Wikipedia says:

在计算机科学中，如果上下文的所有生产规则都采用以下形式，则认为上下文无关的语法为Chomsky范式：

In computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:

• A -> BC 或


• A -> α，或


• S -> ε

• A -> BC, or
• A -> α, or
• S -> ε

其中 A ， B ， C 是非终结符，α是结束符号， S 是开始符号，ε是空字符串。另外， B 和 C 都不是开始符号。

where A, B, C are nonterminal symbols, α is a terminal symbol, S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.

继续您的工作：

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

而不是使用 | 表示不同的选择，将一个规则分为多个规则。

Instead of using | to denote different choices, split a rule into multiple rules.

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb

创建新规则 Y-> a 和 Z-> b ，因为我们很快就会需要它们。

Create new rules Y -> a and Z -> b because we will need them soon.

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

S-> aB 的格式不是 S-> BC ，因为 a 是终端。因此，将 a 更改为 Y ：

S -> aB is not of the form S -> BC because a is a terminal. So change a into Y:

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

对 B->执行相同操作； bb 规则：

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> ZZ
Y -> a
Z -> b

对于 A-> aab ，创建 C-> YY ;对于 B-> bbA ，创建 D-> ZZ ：

For A -> aab, create C -> YY; for B -> bbA, create D -> ZZ:

S0 -> S
S -> AB
S -> YB
S -> B
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

对于 S-> B ，重复一条规则，其中 S 出现在右侧，并内嵌该规则：

For S -> B, duplicate the one rule where S occurs on the right hand side and inline the rule:

S0 -> B
S0 -> S
S -> AB
S -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

使用规则 S0->进行交易； B 和 S0-> S ，将其他规则的右侧连到左侧。另外，删除孤立的规则（LHS符号永远不会在RHS上使用）：

Deal with the rules S0 -> B and S0 -> S by joining the right hand side to the left hand sides of other rules. Also, delete the orphaned rules (where the LHS symbol never gets used on RHS):

S0 -> DA
S0 -> ZZ
S0 -> AB
S0 -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

我们完成了。 ew！

这篇关于将语法转换为Chomsky范式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！