regular-language - 言語が規則的であることを証明する

Question

補題のポンピングは、言語が規則的でないことを証明するために使用されます。しかし、どのようにして言語が
規則的であると証明できるのでしょうか？特に、

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の記事の最初の行を参照してください。