computer-science - 将 CFG 转换为乔姆斯基范式

Question

1. 使用正则语言的抽引引理，证明

   语言 L = { a ⁱ , b ^j c ^k | i, j, k 是非负整数，并且 i=j 或 i=k }

不规则

2. 为上述语言设计 CFG

这就是我想出的

Answer: G = (V,,R, S) with set of variables V = {S,W,X, Y,Z},
where S is the start variable; set of terminals  = {a, b, c}; and rules
S → XY | W
X → aXb | e
Y → cY | e
W → aWc | Z
Z → bZ | e

现在我必须将上面的 CFG 转换为我遇到问题的 chomsky 范式......有什么帮助吗？