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

Question

S --> A | 阿巴 | 抗体

一个--> Aa | 拉姆达

B --> Bb | 公元前

C --> CB | 加利福尼亚州 | bB

我需要帮助将这种语法更改为乔姆斯基正常，这是我想出的答案，但我把它带给了我的教授，他告诉我这是错误的。他拒绝告诉我如何解决它，因为它必须在以后上交。感谢所有帮助。

GL: S→ ZA | AW A→ AA | A B→ AX | YY Z→ a Y→ b X→ YB W→ BZ

Answer 1

我的知识可能生疏了，但我会尽力提供帮助。

根据维基百科，

在形式语言理论中，如果上下文无关文法的所有生产规则都具有以下形式，则称其为 Chomsky 范式：

• A -> BC，或
• A -> α，或
• S -> ε

其中 A、B、C 是非终结符号，α 是终结符号，S 是开始符号，ε 是空字符串。此外，B 和 C 都不能是开始符号。

我正在考虑您的 lambda 是 epsilon ε。让我们把你的语法改写为

S -> A
S -> ABa
S -> AbA
A -> Aa
A -> ε
B -> Bb
B -> BC
C -> CB
C -> CA
C -> bB

然后，添加一个新变量S0作为新的开始变量，这样就变成了

S0 -> S
S  -> A
S  -> ABa
S  -> AbA
A  -> Aa
A  -> ε
B  -> Bb
B  -> BC
C  -> CB
C  -> CA
C  -> bB

接下来，去掉ε规则，就变成了

S0 -> S
S  -> A
S  -> ABa
S  -> AbA
A  -> Aa
B  -> Bb
B  -> BC
C  -> CB
C  -> CA
C  -> bB

引入新变量Y->a和Z->b。

S0 -> S
S  -> A
S  -> ABa
S  -> AbA
A  -> Aa
B  -> Bb
B  -> BC
C  -> CB
C  -> CA
C  -> bB
Y  -> a
Z  -> b

重写 RHS 规则：

S0 -> S
S  -> A
S  -> ABY
S  -> AZA
A  -> AY
B  -> BZ
B  -> BC
C  -> CB
C  -> CA
C  -> ZB
Y  -> a
Z  -> b

引入新变量D->ABand E->AZ，所以它变成

S0 -> S
S  -> A
S  -> DY
S  -> EA
A  -> AY
B  -> BZ
B  -> BC
C  -> CB
C  -> CA
C  -> ZB
D  -> AB
E  -> AZ
Y  -> a
Z  -> b

对于S->A，复制SRHS 上出现的一条规则并内联该规则：

S0 -> S
S0 -> A
S  -> DY
S  -> EA
A  -> AY
B  -> BZ
B  -> BC
C  -> CB
C  -> CA
C  -> ZB
D  -> AB
E  -> AZ
Y  -> a
Z  -> b

S0结合和的规则S。

S0 -> DY
S0 -> EA
S0 -> AY
A  -> AY
B  -> BZ
B  -> BC
C  -> CB
C  -> CA
C  -> ZB
D  -> AB
E  -> AZ
Y  -> a
Z  -> b

现在我们有了乔姆斯基范式的语法。