context-free-grammar - 将 CFG 转换为 CNF

Question

我正在尝试将 CFG 转换为 CNF，但我不确定将什么标识为“变量”。这是问题所在：

S -> aA | ABa 
A -> AA | a  
B -> AbA | bb

我添加了一个新的开始变量来使它

S' -> S  
S -> aA | ABa 
A -> AA | a  
B -> AbA | bb

那么，单位生产去除后，就是：

S' -> aA | ABa 
S -> aA | ABa 
A -> AA | a  
B -> AbA | bb

我知道下一步是更改任何具有超过 2 个变量的产品，但 ABa 是三个变量吗？或者它是两个变量和一个终端？

如果它是两个变量和一个终端，为了最终简化它，我是否能够创建这样的东西：

S' -> aA | Xa  
S -> aA | Xa  
A -> AA | a  
B -> Yb | bb  
X -> AB
Y -> AA

谢谢！

score 0 · Accepted Answer

乔姆斯基范式中的文法具有以下产生式：

A → BC, or
A → a,  or
S → ε,

它由符号 ( a, A...) 组成。这些符号分为两组：终端符号（如a和b，小写字母，都是字母表的一部分）和非终端符号（如A和B，大写字母）。语法也有产生式（如S → a）和起始符号（非终结符）S。

你从这个语法开始（不需要新的开始规则）：

S → aA | ABa
A → AA | a
B → AbA | bb

将串联分离成它们自己的产生式：

S → aA 
S → ABa
A → AA
A → a
B → AbA
B → bb

将所有终端符号移动到它们自己的非终端符号（ainto C（但保留ain A，因为它在 CNF 中已经有效）和binto D）：

S → CA 
S → ABC
A → AA
A → a
B → ADA
B → DD
C → a
D → b

拆分右侧有两个以上非终结符号的位置：

S → CA 
S → AE
A → AA
A → a
B → AF
B → DD
C → a
D → b
E → BC
F → DA

然后你就完成了。

1 回答 1