Automata Theory 简明教程
Chomsky Normal Form
如果产生式满足以下形式，则一个 CFG 处于乔姆斯基范式−
A CFG is in Chomsky Normal Form if the Productions are in the following forms −
-
A → a
-
A → BC
-
S → ε
其中 A、B 和 C 是非终结符，而 a 是终结符。
where A, B, and C are non-terminals and a is terminal.
Algorithm to Convert into Chomsky Normal Form −
Step 1 − 如果起始符号 S 出现在某个右侧，创建一个新的起始符号 S’ 和一个新的产生式 S’→ S 。
Step 1 − If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’→ S.
Step 2 − 删除空产生式。（使用前面讨论的空产生式消除算法）
Step 2 − Remove Null productions. (Using the Null production removal algorithm discussed earlier)
Step 3 − 删除单位产生式。（使用前面讨论的单位产生式消除算法）
Step 3 − Remove unit productions. (Using the Unit production removal algorithm discussed earlier)
Step 4 − 替换每个将 n > 2 替换成 A → B1C 产生的 A → B1…Bn ，将 C → B2 …Bn 替换成 A → B1C 。对右侧有两个或更多符号的每个产生式重复此步骤。
Step 4 − Replace each production A → B1…Bn where n > 2 with A → B1C where C → B2 …Bn. Repeat this step for all productions having two or more symbols in the right side.
Step 5 − 如果任何产生式的右侧形式为 A → aB ，其中 a 是一个终结符且 A, B 是非终结符，那么该产生式被替换为 A → XB 和 X → a 。对形式为 A → aB 的每个产生式重复此步骤。
Step 5 − If the right side of any production is in the form A → aB where a is a terminal and A, B are non-terminal, then the production is replaced by A → XB and X → a. Repeat this step for every production which is in the form A → aB.
Solution
(1) 因为 S 出现在 R.H.S 中，我们添加一个新状态 S0 ， S0→S 被添加到产生式集中并变为 −
(1) Since S appears in R.H.S, we add a new state S0 and S0→S is added to the production set and it becomes −
S0→S, S→ ASA | aB, A → B | S, B → b | ∈
(2) 现在我们将删除空发生式 −
(2) Now we will remove the null productions −
B → ∈和 A → ∈
B → ∈ and A → ∈
在删除了 B → ε 后，产生式集变为 −
After removing B → ε, the production set becomes −
S0→S, S→ ASA | aB | a, A → B | S | ∈, B → b
在删除了 A → ∈ 后，产生式集变为 −
After removing A → ∈, the production set becomes −
S0→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b
(3) 现在我们将删除单元产生式。
(3) Now we will remove the unit productions.
在删除了 S → S 后，产生式集变为 −
After removing S → S, the production set becomes −
S0→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b
在删除了 S0→ S 后，产生式集变为 −
After removing S0→ S, the production set becomes −
S0→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → B | S, B → b
在删除了 A→ B 后，产生式集变为 −
After removing A→ B, the production set becomes −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A → S | b
B→b
B → b
移除 A→S 后，产生式集合变为 −
After removing A→ S, the production set becomes −
S0 → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA
A→b |ASA | aB | a | AS | SA，B→b
A → b |ASA | aB | a | AS | SA, B → b
(4) 现在我们将寻找 R.H.S 中有多个变量的项
(4) Now we will find out more than two variables in the R.H.S
此处，S0→ASA、S→ASA、A→ASA 违反了 R.H.S 中的两个非终结符。
Here, S0→ ASA, S → ASA, A→ ASA violates two Non-terminals in R.H.S.
因此，我们将应用步骤 4 和步骤 5 来获得以下在 CNF 中的最终产生式集合 −
Hence we will apply step 4 and step 5 to get the following final production set which is in CNF −
S0→AX | aB | a | AS | SA
S0→ AX | aB | a | AS | SA
S→AX | aB | a | AS | SA
S→ AX | aB | a | AS | SA
A→b |AX | aB | a | AS | SA
A → b |AX | aB | a | AS | SA
B→b
B → b
X→SA
X → SA
(5) 我们必须更改产生式 S0→aB、S→aB、A→aB
(5) We have to change the productions S0→ aB, S→ aB, A→ aB
最终产生式集合变为 −
And the final production set becomes −
S0→AX | YB | a | AS | SA
S0→ AX | YB | a | AS | SA
S→AX | YB | a | AS | SA
S→ AX | YB | a | AS | SA
A→b A→b |AX | YB | a | AS | SA
A → b A → b |AX | YB | a | AS | SA
B→b
B → b
X→SA
X → SA
Y→a
Y → a