找出在给定上下文无关语法的情况下生成的语言？
我应该手动应用产生式规则来找出该语法生成的语言吗？这很乏味，有什么技巧/技巧可以加快速度吗？
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}
疯狂，不是吗？取自过去的考试（编程语言课程）。
Should I manually apply the production rules to find out the language generated by this grammar? This is tedious, is there any trick/tip to speed up things?
G = {{S, B}, {a, b}, P, S}
P = {S -> aSa | aBa, B -> bB | b}
EDIT: I found Matajon's answer a good one, that is thinking about each language generated by non-terminal symbol and then combine them.
But I'm still stuck when I have to solve some complicated examples like this:
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}
Crazy, isn't it? Taken from past exams (programming languages course).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我不知道任何一般技巧，但通常它有助于思考从每个非终端生成的语言。
在您的示例中，从 B 生成的语言显然是
L(B) = {b}^+。然后你想想S规则，使用第一条规则，你可以生成句子形式{a^nSa^n | n >= 1}。如果您对这些句子形式或单独对 S 使用第二条规则，您可以生成句子形式{a^nBa^n | n >= 1}。休息很简单，你将这两件事结合起来并得到 L(G) = {a^nb^+.a^n | n >= 1}
顺便说一下，在语法的终结符和非终结符的定义中是集合，而不是元组。第三个组成部分是产生式规则，而不是开始符号。所以你应该写
G = {{S, B}, {a, b}, P, S}。编辑
实际上，有一种方法可以解决你的第二个例子，无需太多思考，只需遵循食谱之类的东西即可。因为，第二个上下文无关语法生成的语言实际上是规则的。
当您将 A、B 和 C 的规则替换为前三个规则时，您将得到
And
P'是常规语法。因此，您可以将其转换为非确定性有限自动机（有一个非常简单的方法，寻找它），然后将生成的 NFA 转换为正则表达式（这不是那么简单，但如果您遵循算法并且不会迷失方向） ，你应该没问题）。从正则表达式中可以很容易地看出它描述的是什么语言。另外，一旦你有了这种语言的 NFA，你就可以查看它并确定它的逻辑功能（它与
1,4,7和2,5,8 的计数有关）中的单词和mod 3的区别想清楚了，毕竟这是你的作业:-) ）当然，如果你不使用上下文无关语法生成常规语言。你不能使用这个技巧。没有通用的方法来告诉语法生成什么语言（CFG 的语言相等问题是无法确定的），您必须考虑每个示例并寻找其逻辑结构中的相似性和模式。
I don't know any general trick, but usually it helps to think about the language generated from each non-terminal.
In your example language generated from B is obviously
L(B) = {b}^+. Then you think about S rules, using the first rule, you can generate sentencial forms{a^n.S.a^n | n >= 1}. If you use second rule on these sentencial forms or on S alone you can generate sentencial forms{a^n.B.a^n | n >= 1}.Rest is pretty easy, you combine these two things and get
L(G) = {a^n.b^+.a^n | n >= 1}By the way, in the definition of grammar terminals and nonterminals are sets, not tuples. And third component is production rules, not start symbol. So you should write
G = {{S, B}, {a, b}, P, S}.Edit
Actually, there is a way to solve your second example without much thinking just by following something like a cookbook. Because, language generated by your second context-free grammar is in fact regular.
When you substitute rules for A, B and C to first three rules, you get
And
P'is regular grammar. Because of that, you can convert it to nondeterministic finite automaton (there is really simple way, look for it) and then convert resulting NFA to the regular expression (this is not so simple but if you follow an algorithm and don't get lost, you should be ok). And it from regular expression it is easy to tell what language it describes.Also, once you have NFA for this language you can look at it and determine what it does logically (it has something to do with counts of
1,4,7and2,5,8in the word andmod 3of their difference. Think it through, it is your homework, afterall :-) )Of course, if you don't context-free grammar generating regular language you can't use this trick. There is no general way to tell what language the grammar generates (language equality problem for CFG's is undecideable), you have to think about every single example and look for similarities and patterns in it's logical structure.
我认为你只需要应用生产规则。
I think you'll just need to apply the production rules.