grammar - 上下文无关语法？

Question

我有这个问题，我需要在 CNF 中将以下 CFG 转换为 CFG。

S-> ABa
A-> aab
B-> Ac

我知道步骤如下。

1. 删除 epsilon 转换 - 完成
2. 删除单元制作
3. 通过以下方式转换为 CNF：
   1. 为每个术语引入一个新的非终结符
   2. 用新的非终结符替换产生式规则中的终结符
   3. 引入新的非终结符以减少每个产生式右侧的长度

我对如何解决上述问题感到有些困惑。大多数情况下，我对第 2 步和单元制作感到困惑。

Answer 1

我知道步骤如下。

1. 删除 epsilon 转换 - 完成
2. 删除单元制作
3. 通过以下方式转换为 CNF： 1.为每个术语引入一个新的非终结符
   1. 用新的非终结符替换产生式规则中的终结符
   2. 引入新的非终结符以减少每个产生式右侧的长度

步骤 1 和 2 已经完成。所以我们只需要担心第3步。

起始语法：

S-> ABa
A-> aab
B-> Ac

1. 为每个术语引入一个新的非终结符。

   S  -> ABa
   A  -> aab
   B  -> Ac
   C  -> a
   D  -> b
   E  -> c
   

2. 用新的非终结符替换产生式规则中的终结符。

   S  -> ABC
   A  -> CCD
   B  -> AE
   C  -> a
   D  -> b
   E  -> c
   

3. 引入新的非终结符以减少每个产生式右侧的长度。

   S  -> AF
   A  -> CG
   B  -> AE
   C  -> a
   D  -> b
   E  -> c
   F  -> BC
   G  -> CD
   

Answer 2

S->ABa
C.N.F. is :
M->AB
Z->a
S->MZ

A->aab
C.N.F. is :
X->aa
Y->b
A->XY

B->Ac
C.N.F. is:
K->a
B->AK