证明语言是正常的

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

提供与语言匹配的常规语法或有限自动机.对于可以证明语言是常规的完整属性列表,请参阅维基百科关于常规语言的文章的第一行.