证明一种语言是正规的
泵引理用于证明语言不规则。但是语言可以是怎样的
证明是有规律的？特别是，
Let L be a language. Define half(L) to be
{ x | for some y such that |x| = |y|, xy is in L}.
Prove for each regular L that half(L) is regular.
是否有任何技巧或一般程序来解决此类问题？
Pumping Lemma is used to prove a language to be not regular. But How a language can be
proved to be regular ? In particular,
Let L be a language. Define half(L) to be
{ x | for some y such that |x| = |y|, xy is in L}.
Prove for each regular L that half(L) is regular.
Is there any trick or general procedure to tackle such kind of questions ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您可以通过 NFA 或 DFA，那么它将是常规的。
NFA、DFA、正则语法和正则表达式，因此 L 在任何这些形式中的表示都应该可以。
If you can correctly describe your language L by an NFA or DFA, then it will be regular.
There is a well known equality of NFAs, DFAs, regular grammars and regular expressions, so a representation of L in any of these formalisms should do.
提供与该语言匹配的正则语法或有限自动机。有关可以证明语言是常规语言的属性的完整列表，请参阅关于常规语言的维基百科文章的第一行语言。
Provide a regular grammar or a finite automaton that matches the language. For the full list of properties you can prove to show a language is regular, see the first lines of the Wikipedia Article on regular languages.