computer-science - 乔姆斯基范式转换

Question

我需要你尽快的帮助。我应该转换为乔姆斯基范式。

S -> 01S | XY

X -> 110Y | 0 | ε

Y -> YY | 1

我尝试过很少，但我总是卡住，因为我有这些混合部件，例如 110Y ......

Answer 1

有点晚了，但还是尽快：

开始语法：

S → 01S | XY
X → 110Y | 0 | ε
Y → YY | 1

将串联拆分为单独的产生式：

S → 01S
S → XY
X → 110Y
X → 0
X → ε
Y → YY
Y → 1

删除 epsilon（内联X）：

S → 01S
S → 110YY
S → 0Y
S → Y
Y → YY
Y → 1

删除生产S → Y：

S → 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

然后你就完成了。