regular-language - 证明一种语言是正规的

Question

Pumping Lemma 用于证明语言不规则。但是如何
证明一种语言是正则的呢？尤其是，

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.  

是否有任何技巧或一般程序来解决此类问题？

Answer 1

如果您可以通过NFA或DFA正确描述您的语言 L ，那么它将是常规的。

NFA、DFA、正则文法和正则表达式有一个众所周知的相等性，因此任何这些形式中的 L 表示都应该这样做。

Answer 2

提供与语言匹配的正则文法或有限自动机。有关您可以证明显示一种语言是常规的属性的完整列表，请参阅有关常规语言的Wikipedia 文章的第一行。