grammar - 为 CFL 编写 GNF 语法

Question

你好我想问你这个问题。

我应该（手动）计算格雷巴赫范式中的语法，生成语言

L = {ai bj ck | i + j = 2k and k >= 1}

我真的不知道。有人可以帮帮我吗？

提前
谢谢克里斯

Answer 1

适合您的语言的上下文无关语法 CFG 。 La = {ai bj ck | i + j = 2k and k >= 1}

以下是用语言回答。 L = {ai bj ck | i + j = k and k >= 1}

配置文件：

S --> aAc | bBc |
A --> aAc | B   |  ^
B --> bBc | ^ 

什么是 GNF？

CFG 的一种重要形式是 Greibach Normal Form GNF：

   A --> aα   
   Where α ∈ V* (any number of variables including zero)

注意： nul^不能是任何产生式的 RHS 上的符号接受S带有 constrict 的开始符号，如果S --> ^是语法中的产生式，则S不能出现在任何其他语法产生式的 RHS 上。

任何 CFG 都可以写成 GNF 形式。

如何在 GNF 中转换 CFG？

请注意，我在上面写的 CFG 中有 nul 产品A --> ^和B --> ^一个 Unit 产品A --> B。GNF 形式中不允许单位产生式和 nul 产生式。尽管通过在语法中引入 GNF 产生式可以很容易地以 GNF 形式编写其他产生式，例如S --> aAc 可以重写为S --> aAC and C --> c.

所以下面我正在为语言重写等效的 CFG，并删除称为简化 CFG 的 nul 和单位产品。

简化配置文件：

S --> aAc | bBc | ac | bc
A --> aAc | bBc 
B --> bBc | bc

现在，通过引入新的 GNF 产生式并在其他产生式规则中C --> c替换c为，可以轻松地将这种语法转换为 GNF 形式。C

语言 L 的 GFN：

S --> aAC | bBC | aC | bC
A --> aAC | bBC 
B --> bBC | bC
C --> c

^{错误地我写了一个错误的语法我会更新语言的答案L_a}

编辑

La = {ai bj ck | i + j = 2k and k >= 1}.

L _{a 的}CFG ：

S --> aaAc | bbBc | abBc
A --> aaAc | B    | abBc |  ^
B --> bbBc | ^ 

简化配置文件：

S --> aaAc | bbBc | abBc | aac | bbc | abc 
A --> aaAc | bbBc | abBc | aac | abc
B --> bbBc | bbc 

_{语言 L a 的}GFN ：

添加三个新的生产规则X --> a：Y --> b和Z --> c。

更改程序员并用变量替换终端：

S --> aXAZ | bYBZ | aYBZ | aAZ | bYZ | aYZ  
A --> aXAZ | bYBZ | aYBZ | aXZ | aYZ
B --> bYBZ | bYZ
X --> a
Y --> b
Z --> c

Answer 2

关于下面的答案 CFGLa = {ai bj ck | i + j = k and k >= 1}是错误的

您的简化 CFG：

S --> aAc | bBc | ac | bc . A --> aAc | bBc . B --> bBc | bc .

因为上面的语言L = {ai bj ck | i + j = k and k >= 1}会产生语言aabccc，但您的 Simplified CFG 不会产生它。

右 CFG 是

简化的 CFG

S --> aAc | bBc | ac | bc A --> aAc | bBc | bc | ac B --> bBc | bc

纠正一下，第二语言也有同样的问题。

谢谢！