定期的集合の有限和組としての正規言語

Question

は、すべての正規言語が定期セットの有限の連合として表現できることが本当ですか？言い換えれば、 $ l $ が定期的にある場合は、有限セット $ a_1、\ dots、a_n、b_1を存在します。、\ dots、b_n $ そのような

$$ l= A_1 \ CDot B_1 ^ * \ cup \ cdot \ cup a_n \ cdot b_n ^ *。$$

私はこれが正規のアルファベットを介した通常の言語に当てはまることを知っていますが、一般的なアルファベットをよくわからない。

Answer 1

このフォームのすべての言語は、入れ子になったKleene Starのない正規表現として表現できます。つまり、その star height は。スターハイト階層は厳密であり、特に言語 $（a ^ * b ^ * c）^ * $ はその形式では表現できません。バイナリアルファベットの例は $（aa（ab）^ * bb（ab）^ *）^ * $ です。

Answer 2

@YUVALFILMUSによる回答は完全に大丈夫で、スターの高さの輸入概念を指しています。しかし、もう少し追加しましょう。私たちはあなたのフォームの言語がスターハイトの言語の適切なサブセットを与えることを示します。しかし、最初に、何人かのマスがあなたのフォームに近づくかもしれないものです。

<強力>一般的な定期言語

最初に、おそらく、通常の $ l \ subseteq \ sigma ^ * $ 、完全な決定論的オートマトン $ A=（\ SIGMA、Q、\ Delta、Q_0、F）$ 。 $ q $ x¥¥¥¥¥¥¥¥Subseteq q $ e¥subseteq q $ 、 $ l_ {q、e}（a）$ 言語の $（\ sigma、q、\ delta、q、e）$ 、つまり開始状態を変更する $ Q $ そして、最終状態のセット $ e $ へのセット。 それから、私たちは書くことができます $$ l=bigcup_ {q \ in f} L_ {q_0、q}（a）l_ {q、\ {q \}}}}}}}（a）^ * $$ この結果は民間伝承のようで、簡単に続きます。交換することで、少し強化することができます $ l_ {q_0、\ {q \}}（a）$ $$ \ {u \ in l_ {q_0、\ {q \}} \ mid \ delta（q_0、v）\ Ne q \ mbox {$ u $ v $ $ u $} \} $$ 上記の式で。それに単語が別の単語の適切な接頭辞であるという財産を持っています。この分解の変形、およびより多くの改良は、のオートマトン、言語、およびマシン、音量A 、S.Eilenbergによって、繰り返しアップ分解。< / P>

換算定期的かつ制限された正規言語

他の人は、あなたが述べられている単項の唯一の言語ケースの適切な一般化を行い、制限された定期的な言語のための適切な一般化をすることができます。言語は、それが文字の置換の下で閉じられているならば、変換です。たとえば、 $ \ {ab、ba \} $ は変換ですが、 $ \ {ab \} $ ではありません。言語 $ l \ subseteq \ sigma ^ * $ は、 $ l \ subeteqの場合、 bounded です。 W_1 ^ * \ CDOTS W_N ^ * $ 言葉の場合 $ w_i \ in \ sigma ^ * $ 。次のようにして、 $ \ diamond $ 2つの言語のシャッフル、 $ l \ subseteq \ sigma ^ * $ 、 $ l ^ {\ diamond、*}=bigcup_ {n \ ge 0} \ underbrace {l \ Diamond \ Ldots \ Diamond L} _ {\ mbox {$ n $ times}} $ 繰り返しシャッフル。また、 $ \ operatorname {perm}：2 ^ {\ sigma ^ *} \ ~2 ^ {\ sigma *} $ は置換クロージャーを表します。 / em>、またはの変換閉鎖、つまり順列なしのすべての単語を追加します。 たとえば、 $ \ operatorname {perm}（\ {ab \}）={ab、ba \} $ 。

$ l \ subseteq w ^ * $ は通常のIFF $ l= w ^ n（w ^ p $ n、p \ ge 0 $ の場合）^ * $ 。これは、 $ \ {n：w ^ n \} $ が最終的に定期的に（定期的な言語として見ることができます）。 / P>

$ l \ subeteq w_1 ^ * \ cdots w_r ^ * $ は通常のIFFです。 $ L_1 \ CDOTS L_R $ 、各 $ l_i \ subseteq w_i ^ * $ は通常です。

また、 $ \ sigma={a_1、\ ldots、a_k \} $ と $ l \ subeteq \ Sigma ^ * $ は変換された定期的です、それは可能な $$ l=bigcup_ {i= 1} ^ n \ operatorname {perm}（u_i）\ diamond \ operatorname {perm}（n_i）^ {\ diamond、*} $$ 有限セットの場合 $ n_i \ subseteq a_1 ^ * \ cup \ ldots \ cup a_k ^ * $ $ | n_i \ cap a_j ^ * | .. \ LE 1 $ 。

また、述べられているようにここでと< href="https://arxiv.org/abs/2005.04042" REL="NOFOLLOW NOREFERRER">ここ、通常の言語 $ l $ $ \ sigma={a_1、\ ldots、a_k \} $ は転和IFFです $$ l=bigcup_ {i= 1} ^ n u_ {i,1} \

ダイヤモンド\ Ldots \ Diamond u_ {i、k} $$ 単項の正規言語の場合 $ u_ {i、j} \ subseteq a_j ^ * $ $ i \ in \ {1、\ ldots、n} $ と $ j \ in \ {1、\ LDOTS、K \} $ 。

これらすべての結果は密接に関連しています。単項言語の場合、それらはすべて述べたフォームに減少します。

あなたのフォームの言語のための必要条件

状態の状態はトポロジと無限の単語を含みます。 $ b ^ * $ 、 $（b ^ * a）^ * $ あなたのフォームに書かれなかった。後者は星の高さ2を持ち、スターの高さはサイクルランクによって特徴付けることができます。 Egganの定理。 しかし、私は星の高さに基づいていない、ここでは、自己完結型、ここでは違う議論をしたいです。 $ \ sigma ^ {\ omma} $ $ \ sigma $ の一連の無限単語です。演算子を定義します。 $ w：2 ^ {\ sigma ^ *} \ 2 ^ {\ sigma ^ {\ ommga}}} $ by、 $ l \ subseteq \ sigma ^ * $ 、 $$ w（l）={\ xi \ in \ sigma ^ {\ omma} \ mid \ mbox {$ \ xi $は無限に多くのプレフィックスが$ l $} \}です。 $$ それから \ begin {align *} w（b ^ * a）＆=emptyset \\ w（（b ^ * a）^ *）＆={\ xi \ in \ sigma ^ {\ omega} \ mid \ mbox {$ \ xi $は無限に多くの$ A $です。 } \ \}。 \ end {align *} それを観察してください $$ w（u \ cup v）= w（u）\ cup v（v）、 $$ $ \ xi \ in w（u \ cup v）$ の場合、PigenHoleの原則によって、少なくとも1つの $ u $ または $ v $ 、またはその両方に、 $ \ xiの優れたプレフィックスを含める必要があります。 $ 。また、あなたの形式では、連結がユニオンを販売するにつれて、すべてのセット $ a_i $ はシングルトンです。

フォーム $ l= u（u_1 + \ ldots + u_n）^ * $ の言語を検査します。これは、フォームの一部です。 set $ \ gamma={b_1、\ ldots、b_n \} $ 、補助アルファベット、および同型 $を考える。 h：\ gamma \ to \ sigma ^ * $ $ h（b_i）= u_i $ 、つまり各文字を対応する単語で置き換えます。この同型性は、 $ \ gamma ^ {\ omega} $ の無限の単語にも適用できます。我々は持っています $$ w（u（u_1 + \ ldots + u_n）^ *）={uh（\ xi）\ mid \ xi \ in \ gamma ^ {\ omega} \}。 $$ 特に、すべてのセット $ b_i $ がシングルトンの場合、 $ w（l）$ は有限です。 $ w（l）\ ne \ ustyset $ あなたのフォームのあらゆる無限言語です。

最後の観察によって、 $ b ^ * $ をあなたの形式で書くことができませんでした。だから、これは非常に簡単な例です、星の高さ1でさえ。 しかし、 $ l=（b ^ * a）^ * $ もそのように書かれていないことを示しましょう。それがすべて無限の単語を持つ可能性があると仮定します。これには、無限数の $ a $ がありますが、正同素化の観点から書くことができます。 $ H：\ GAMMA ^ * \ \ SIGMA ^ * $ 上記のように、すなわち $$ \ {\ xi \ in \ sigma ^ {\ omma} \ mid \ mbox {$ \ xi $は無限に多くの$ A $です。= u H（\ gamma ^ {\ omega}） $$ 一部の $ u \ in \ sigma ^ * $ の場合 $ m={| h（x）| ：x \ in \ gamma \} + | u | $ 。 その後、 $ ub ^ maaaaa \ cdot $ はこの言語にあります、 これは $ + $ を意味します。 $ x \ in \ in \ in \ in \ in \ insp >。 しかし、 $ ubbbbbbb \ cdots \ in uh（\ gamma ^ {\ ommga}）$ は、矛盾である $ A $ の。したがって、 $（b ^ * a）^ * $ をその方法で書くことができませんでした。 $ \ square $