找出生成的语言，给出一个上下文无关的语法？

Question

我应该手动应用生产规则来找出这种语法所生成的语言吗？这很乏味，有什么窍门可以加快速度吗？

G = {{S, B}, {a, b}, P, S}
P = {S -> aSa | aBa, B -> bB | b}

编辑：我发现Matajon的答案是一个很好的答案，那就是考虑由非终端符号生成的每一种语言，然后将它们结合起来。

但是当我不得不解决一些复杂的例子时，我仍然被困住了：

G = {{S, R, T}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, P, S}

P = {S -> A | AS | BR | CT,
     R -> AR | BT | C | CS,
     T -> AT | B | BS | CR,
     A -> 0 | 3 | 6 | 9,
     B -> 1 | 4 | 7,
     C -> 2 | 5 | 8}

太疯狂了，不是吗？摘自过去的考试(编程语言课程)。

Answer 1

我不知道任何一般的技巧，但通常它有助于思考从每个非终端产生的语言。

在您的示例中，B生成的语言显然是L(B) = {b}^+。然后考虑S规则，使用第一条规则，可以生成句子形式{a^n.S.a^n | n >= 1}。如果您对这些句子形式使用第二条规则，或者仅在S上使用第二条规则，则可以生成句子形式{a^n.B.a^n | n >= 1}。

Rest非常容易，您可以将这两件事结合起来并获得L(G) = {a^n.b^+.a^n | n >= 1}

顺便说一句，在语法终末和非终末的定义中，都是集，而不是元组。第三个组成部分是生产规则，而不是开始符号。所以你应该写G = {{S, B}, {a, b}, P, S}。

编辑

实际上，有一种方法可以解决你的第二个例子，而不需要太多的思考，只需遵循一些类似于食谱的东西。因为，第二个上下文无关语法生成的语言实际上是规则的。

当你把A，B和C替换成前三条规则时，你会得到

P' = {S -> 0 | 3 | 6 | 9 | 0S | 3S | 6S | 9S | 1R | 4R | 7R | 2T | 5T | 8T
     R -> 0R | 3R | 6R | 9R | 1T | 4T | 7T | 2 | 5 | 8 | 2S | 5S | 8S
     T -> 0T | 3T | 6T | 9T | 1 | 4 | 7 | 1S | 4S | 7S | 2R | 5R | 8R}

P'是规则语法。因此，您可以将其转换为非确定性有限自动机(有非常简单的方法，查找它)，然后将生成的NFA转换为正则表达式(这并不简单，但如果您遵循一个算法，并且不迷路，您应该没事)。它从正则表达式中很容易分辨出它所描述的语言。

此外，一旦您为这种语言拥有了NFA，您就可以查看它并确定它在逻辑上做了什么(它与单词中的1,4,7和2,5,8的计数以及它们之间的差异的mod 3有关。仔细想想，这是你的家庭作业，毕竟:-)

当然，如果您不使用上下文无关的语法生成常规语言，您就不能使用这个技巧。没有通用的方法来判断语法产生了什么语言(CFG的语言平等问题是无法判定的)，你必须考虑每一个例子，并在它的逻辑结构中寻找相似之处和模式。

Answer 2

我想你只需要应用生产规则。