我需要尽快得到你的帮助。 我应该转换为乔姆斯基范式。
S -> 01S | XY
X -> 110Y | 0 | ε
Y -> YY | 1
我尝试了几次，但我总是陷入困境，因为我有这些混合的部分，例如110岁...
有点晚了，但还是尽快:
起始语法：
S → 01S | XY
X → 110Y | 0 | ε
Y → YY | 1
将串联拆分为单独的产生式：
S → 01S
S → XY
X → 110Y
X → 0
X → ε
Y → YY
Y → 1
删除 epsilon（内联
XS → 01S
S → 110YY
S → 0Y
S → Y
Y → YY
Y → 1
取消生产
S → YS → 01S
S → 110YY
S → 0Y
S → YY
S → 1
Y → YY
Y → 1
用右侧具有该符号的新产生式替换所有端子符号：
S → ABS
S → BBAYY
S → AY
S → YY
S → 1
Y → YY
Y → 1
A → 0
B → 1
打破右侧有两个以上非终结符的所有产生式：
S → CS
S → DE
S → AY
S → YY
S → 1
Y → YY
Y → 1
A → 0
B → 1
C → AB
D → BB
E → AF
F → YY
然后你就完成了。
转换乔姆斯基范式的算法::
步骤 1 - 如果开始符号 S 出现在右侧，则创建一个新的开始符号 S' 和一个新的产生式 S'→ S。
第 2 步 - 删除空产生式。 （使用前面讨论的空产生式去除算法）
第 3 步 - 删除单位产生式。 （使用前面讨论的单位生产去除算法）
步骤 4 - 将每个产生式 A → B1…Bn（其中 n > 2）替换为 A → B1C（其中 C → B2 …Bn）。对右侧有两个或多个符号的所有产生式重复此步骤。
步骤 5 - 如果任何产生式的右侧采用 A → aB 的形式，其中 a 是终结符，A、B 是非终结符，则产生式将替换为 A → XB 和 X → a。对每个 A → aB 形式的产生式重复此步骤。
问题：
将以下CFG转换为CNF
S → ASA | aB, A → B | S，B → b | ε
解决方案 (1) 由于S出现在R.H.S中，我们添加一个新的状态S0，并且S0→S被添加到生产集中，它变成-
S0→S，S→ ASA | aB, A → B | S，B → b | ε
(2) 现在我们将删除空产生式 -
B → ε 且 A → ε
去掉B→ε后，产生式集变为−
S0→S，S→ ASA |乙 | a, A → B | S | ε, B → b
去掉A → ε 后，产生式集变为−
S0→S，S→ ASA |乙 |一个 |作为 |南澳 | S，A → B | S、B → b
(3) 现在我们将删除单元产生式。
去掉S→S后，产生式集变成−
S0→S，S→ ASA |乙 |一个 |作为 |南，A → B | S、B → b
去掉S0→S后，产生式集变为−
S0→ ASA |乙 |一个 |作为 | SA、S→ ASA |乙 |一个 |作为 |萨
A → B | S、B → b
去掉A→B后，产生式集变成−
S0 → ASA |乙 |一个 |作为 | SA、S→ ASA |乙 |一个 |作为 |萨
A → S |
B → b
去掉A→S后，产生式集变成−
S0 → ASA |乙 |一个 |作为 | SA、S→ ASA |乙 |一个 |作为 |萨
A → b |ASA |乙 |一个 |作为 | SA，B → b
(4) 现在我们将在 R.H.S 中找出两个以上的变量
这里，S0→ ASA，S → ASA，A→ ASA 违反了 R.H.S. 中的两个非终结符
因此，我们将应用步骤 4 和步骤 5 来获得以下 CNF 中的最终产生式集 -
S0→ AX |乙 |一个 |作为 |萨
S→ AX |乙 |一个 |作为 |萨
A → b |AX |乙 |一个 |作为 |萨
B → b
X→SA
(5) 我们必须改变产生式 S0→ aB, S→ aB, A→ aB
最终的生产集变成 -
S0→ AX | YB |一个 |作为 |萨
S→ AX | YB |一个 |作为 |萨
A → b A → b |AX | YB |一个 |作为 |萨
B → b
X→SA
Y→a
Transformasikan tata bahasa bebas konteks berikut ke dalam Bentuk 正常乔姆斯基
S→ abAB
AbAB |ε
B BAa |ε
*Lakukan penyederhanaan terlebih dahulu！