根据上下文无关的语法找出生成的语言？

我应该手动应用生产规则来找出这个语法生成的语言吗？这很乏味，是否有任何技巧/提示加快速度？根据上下文无关的语法找出生成的语言？

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}

疯狂，不是吗？从过去的考试（编程语言课程）采取。

来源

2011-01-24 gremo

逗号是此语言版本的缩写本吗？ – Davidann 2011-01-24 19:16:56

@Matajon不，这是我的不好。我编辑了文本以修复不正确的定义。谢谢。 – gremo 2011-01-24 20:46:27

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

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

休息是很容易的，你把这两件事情，并得到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的语言平等问题是不可否认的），你必须考虑每一个例子，并在它的逻辑结构中寻找相似点和模式。

来源

2011-01-24 19:33:26

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

来源

2011-01-24 19:16:19 Davidann

根据上下文无关的语法找出生成的语言？

回答

相关问题