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，regular grammars和regular expressions具有众所周知的相等性，因此在这些形式主义的任何形式中都应使用L的表示形式。