将语法转换为乔姆斯基范式？

Question

将以下语法转换为乔姆斯基范式。给出所有中间步骤。

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

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

所以现在我

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

删除了所有的 lambda 规则：

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

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

Answer 1

维基百科说：

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

• A -> 公元前，或
• A -> α，或
• S -> ε

其中 A、B、C 是非终结符号，α 是终结符号，S 是起始符号，ε 为空串。此外，B 和 C 都不能是起始符号。

继续你的工作：

<前><代码>S0 -> S
S-> AB |乙 |乙
A->阿布
B->工商管理学士 | BB

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

<前><代码>S0 -> S
S-> AB
S->乙
S->乙
A->阿布
B->工商管理学士
B-> BB

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

<前><代码>S0 -> S
S-> AB
S->乙
S->乙
A->阿布
B->工商管理学士
B-> BB
Y->一个
Z->乙

<代码>S - > aB 的形式不是 S ->; BC 因为 a 是一个终端。因此将 a 更改为 Y：

<前><代码>S0 -> S
S-> AB
S-> YB
S->乙
A->阿布
B->工商管理学士
B-> BB
Y->一个
Z->乙

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

<前><代码>S0 -> S
S-> AB
S-> YB
S->乙
A->阿布
B->工商管理学士
B-> ZZ
Y->一个
Z->乙

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

<前><代码>S0 -> S
S-> AB
S-> YB
S->乙
A->捷克
C-> YY
B-> DA
D-> ZZ
B-> ZZ
Y->一个
Z->乙

对于 S -> B，复制右侧出现 S 的一条规则并内联该规则：

<前><代码>S0 ->乙
S0-> S
S-> AB
S-> YB
A->捷克
C-> YY
B-> DA
D-> ZZ
B-> ZZ
Y->一个
Z->乙

处理规则S0 -> B 和 S0 -> S 通过将其他规则的右侧连接到左侧。另外，删除孤立的规则（其中 LHS 符号永远不会在 RHS 上使用）：

<前><代码>S0 -> DA
S0-> ZZ
S0-> AB
S0-> YB
A->捷克
C-> YY
B-> DA
D-> ZZ
B-> ZZ
Y->一个
Z->乙

我们就完成了。唷！

Answer 2

在不涉及太多理论和证明的情况下（您可以在维基百科中查看），将上下文无关语法转换为乔姆斯基范式时必须做一些事情，通常必须执行四个范式转换。首先，您需要直接或间接地识别所有可以产生空字符串（lambda/epsilon）的变量 - （Lambda-Free 形式）。其次，您需要删除单元产生式 - （无单元形式）。第三，你需要找到所有活跃/有用（有用性）的变量。四、需要找到所有可达符号（Reachable）。在每一步中，您可能会也可能不会有新的语法。因此，对于你的问题，这就是我想出的...

---

上下文无关语法

G(Variables = { A B S }
Start = S 
Alphabet = { a b lamda}

Production Rules = { 
S  ->  |  AB  |  aB  |  
A  ->  |  aab  |  lamda  |  
B  ->  |  bbA  |   } )

删除 lambda/epsilon

ERRASABLE(G) = { A }

G(Variables = { A S B }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  B  | 
B  ->  |  bbA  |  bb  |   } )

删除单元生成

UNIT(A) { A }
UNIT(B) { B }
UNIT(S) { B S }
G (Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

确定活动符号

LIVE(G) = { b A B S a }

G(Variables = { A B S }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

删除无法访问

REACHABLE (G) = { b A B S a }
G(Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

用实心非终结符替换所有混合字符串

G( Variables = { A S B R I }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IIA  |  
A  ->  |  RRI  |  
B  ->  |  IIA  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |   })

乔姆斯基范式

G( Variables = { V A B S R L I Z }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IV  |  
A  ->  |  RL  |  
B  ->  |  IZ  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |  
L  ->  |  RI  |  
Z  ->  |  IA  |  
V  ->  |  IA  |   })

Answer 3

替代答案：语法只能产生有限数量的字符串，即 6 个。

 S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb.

您现在可以手动将其压缩回乔姆斯基范式。

---

通过替换，我们可以找到所有产生的字符串的集合。你的初始规则：

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

首先拆分 S 规则：

S -> AB.
S -> aB.

现在将 A 和 B 展开替换为：

S -> AB
  -> (aab | lambda) bbA
  -> (aab | lambda) bb (aab | lambda).
S -> aB
  -> abbA
  -> abb (aab | lambda).

再次展开这些得到：

S -> aabbbaab.
S -> aabbb.
S -> bbaab.
S -> bb.
S -> abbaab.
S -> abb.

---

要将这个有限集更改为乔姆斯基范式，只需通过暴力破解即可没有任何智能因素的力量。首先，我们引入两个终端规则：

X -> a.
Y -> b.

现在，对于每个字符串，我们使用终端变量使用第一个字母，使用新变量使用其余字母。例如，像这样：

S -> aabbb. (initial rule, not in Chomsky Normal Form)

S -> XC, where X->a and C->abbb.
C -> XD, where X->a and D->bbb.
D -> YE, where Y->b and E->bb.
E -> YY, where Y->b and Y->b.

我们只是对所有 6 个字符串进行这个过程，生成很多新的中间变量。