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

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 - > 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

我们已经完成了.唷!

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  |   })