將語法轉換爲喬姆斯基的正常形式

Question

S - > A | ABa | AbA

A - > Aa | lambda

B - > Bb | BC

C - > CB | CA | bB

我需要幫助改變這個語法爲喬姆斯基正常，這是我想出的答案，但我把它給我的教授，他告訴我這是錯的。他拒絕告訴我如何解決這個問題，因爲它必須晚些時候上交。所有的幫助表示讚賞。

GL：S→ZA | AW A→AA |一個B→AX | YY Z→a Y→b X→YB W→BZ

Answer 1

我的知識可能會生鏽，但我會盡力幫忙。

根據維基百科，

在形式語言理論，一個上下文無關文法被認爲是喬姆斯基範式，如果它的所有生產規則的形式爲：

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

其中A，B，C是非終端符號，α是終端符號，S是開始符號，ε是空字符串。而且，B和C都不是開始符號。

我在考慮你的lambda是epsilon ε。讓我們來修改你的語法

S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
A -> ε 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

然後，添加一個新的變量S0作爲新的起點變量，因此它成爲

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
A -> ε 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

然後，取下ε規則，因此它成爲

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

引入新變量Y->a和Z->b。

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 
Y -> a 
Z -> b 

重寫RHS規則：

S0 -> S 
S -> A 
S -> ABY 
S -> AZA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
Y -> a 
Z -> b 

引入新的變量D->AB和E->AZ，因此它成爲

S0 -> S 
S -> A 
S -> DY 
S -> EA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

對於S->A，複製其中S發生在RHS和內嵌的一個規則規則：

S0 -> S 
S0 -> A 
S -> DY 
S -> EA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

合併規則S0和S。

S0 -> DY 
S0 -> EA 
S0 -> AY 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

現在我們有了喬姆斯基正常形式的語法。