如何查找 CFG 生成的语言
如果给出了上下文无关语法，是否有一种系统的方法来找出生成的语言并使用描述性而不是分析的方式将其表达为一个集合，例如 L(G)={0^ n.1^n|n?=1} （而不是 L(G)={01,0011,000111,...}）？
我实际上问这个问题是因为如果给出了 CFG 并且存在这样的问题：“找到语法的语言。证明/证明你的答案。” ，那么某人如何证明/证明他/她的答案呢？
If a Context-Free Grammar is given, is there a systematic way to find out the generated language and express it as a set using a descriptive and not analytic way, like L(G)={0^n.1^n|n?=1} (and not L(G)={01,0011,000111,...}) ?
I actually ask because if a CFG is given and there is a question like: "Find the language of the grammar.Prove/Justify your answer." , then how can someone prove/justify his/her answer otherwise?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一般来说，没有。例如，对于任意上下文无关语法，该语言是否等价于 Sigma* 的问题是不可判定的——这就是最简单的
人们可能会想到 CFL 的描述。另一个无法确定的问题是
两个上下文无关语法 A 和 B 定义相同的语言，这不是好兆头
对于更普遍的问题，即语法和其他一些替代表示是否定义相同的语言。
在特定情况下，此类问题可能是可以判定的——对于正式语言理论的学生来说幸运的是！但根据上述可判定性结果，你不会发现
一个简单的算法，可以让你从语法到语言理论教科书中通常出现的那种简洁描述。这更多的是一个反复试验的过程，其中
您使用一些直觉来想出候选描述，然后应用更正式的方法，例如构建解析树，或使用闭包属性或抽引理，来证明或反驳等价性。
In general, no. For example, for an arbitrary context free grammar, the question of whether the language is equivalent to Sigma* is undecidable -- and that's about the simplest
description of a CFL one might imagine. Another undecidable question is whether
two context free grammars A and B define the same language, which doesn't bode well
for the more general question of whether a grammar and some other alternate presentation define the same language.
In specific cases, such questions may be decidable -- fortunately for formal language theory students! But in light of the above decidability results, you're not going to find
a simple algorithm that gets you from a grammar, to a concise description of the sort usually presented in language theory textbooks. It's more of a trial and error process, where
you use some intuition to think up a candidate description, then apply the more formal methods like building parse trees, or using closure properties or pumping lemmas, to prove or disprove the equivalence.