言語を定期的に証明する

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

あなたがあなたの言語を正しく説明できるならl NFA また DFA, 、それは定期的になります。

NFAS、DFASのよく知られている平等があります。 通常の文法 と 正規表現, 、したがって、これらの形式主義のいずれかにおけるLの表現を行う必要があります。

Answer 2

言語に一致する定期的な文法または有限のオートマトンを提供します。プロパティの完全なリストについては、言語が定期的であることを示すことを証明できます。 ウィキペディアの記事 通常の言語で。