10

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

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键入不存在的规则。这就是我想出的答案，我需要做进一步的事情还是我做错了什么？

4

3 回答 3

20

维基百科说：

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

  • A -> BC，或
  • A -> α，或
  • S -> ε

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

继续你的工作：

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

与其|用来表示不同的选择，不如将一个规则拆分为多个规则。

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

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

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：

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：

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右侧出现的一条规则并内联该规则：

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 上使用）：

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

我们完成了。呸！

于 2011-09-19T00:28:58.550 回答
6

无需过多理论和证明（您可以在 Wikipedia 中查看此内容），将上下文无关语法转换为乔姆斯基范式时必须做一些事情，通常必须执行四个范式转换。首先，您需要确定所有可以直接或间接产生空字符串（lambda/epsilon）的变量（无 Lambda 形式）。其次，您需要删除单元制作 - （Unit-Free form）。第三，您需要找到所有有效/有用的变量（有用性）。四、你需要找到所有的可达符号（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  |   })
于 2011-09-21T10:47:36.497 回答
1

替代答案：语法只能产生有限数量的字符串，即 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 个字符串进行了这个过程，生成了很多新的中间变量。

于 2011-09-19T00:52:42.260 回答