我如何构建生成这种语言的语法？上下文无关文法

Question

我正在学习有限自动机和语法测试，我被这个问题卡住了：

构造一个生成L的文法:l= {a^n b^m c^2n | n>=0，m>=0}

我如何构建生成这种语言的语法？文法上下文无关文法自动机

Answer 1

我认为这应该能起到作用。我在http://mdaines.github.io/grammophone/上验证过了。

S -> a B c c|a S c c|。

B -> b B|。

Answer 2

我发现，对于这类问题，想出一些规则来从小字符串中构建大字符串总是有帮助的。首先，找出你语言中最小的字符串。在我们的例子中，我们可以从这样的观察开始:如果n= 0，那么b^m在我们的语言中；也就是说，b*中的w在我们的语言中。然后我们注意到，如果x在我们的语言中是一个字符串，我们通过在左侧添加一个a和在右侧添加两个cs来获得另一个字符串；也就是说，axcc在我们的语言中也是一个字符串。所以我们的规则是：

1. b* in L
2. if x in L then axcc in L

现在，用CFG编写这段代码很简单：

S -> B
S -> aScc

这里，S生成我们的语言L，B生成语言b*。我们通过提供以符号B开始的b*的语法来完成语法：

(1) S -> B
(2) S -> aScc
(3) B -> e
(4) B -> B

任何字符串a^n b^m c^2n都可以使用规则2的n个应用程序、规则1的1个应用程序、规则4的m个应用程序和规则3的1个应用程序来生成。作为练习，此语法不生成不在语言中的字符串。