L *が正規の言語であることを証明する

Suppose that L is any language , not necessarily regular, whose
alphabet is {0}; that is the strings of L consist of 0’s only.
Prove that L* is regular.enter image description here

ベストアンサー

私はそれが研究レベルの質問ではないと信じています。

次のように進めることができます。まず、$ L ^ * = L_ {fin} となるような$ i、j in mathbb
{N} $が存在することを証明することができます。カップ {0 ^ {j + kn} ; | ; n in
mathbb {N} } $と$ L_ {fin}
$は有限の言語です(従って規則的です)。あなたがそれを知ったら、適切なオートマトンを構築するのは簡単です。

それを証明するために、自然数として$ 0 ^ *
$からの要素を考えることができ、ユークリッドアルゴリズムを使用することができます。あなたは$ k = gcd(y_1、
ldots、y_l)$のように、あなたのセットのgcdとして$ k $といくつかのジェネレータのセットとして$ y_1、y_2、
ldots y_l $を取ることができます。 $ j $を得るためには、$ sum_ {i = 0} ^ {n} b_iy_i
のような非ゼロの数$ b_i $があることが分かります。 text {mod} ; y = k $とし、$ j = Pi_
{i = 0} ^ ly_i cdot sum_ {i = 0} ^ {n} b_iy_i $を取る。言語$ L_ {fin}
$は$ L ^ * $から$ j $より小さい単純な要素です。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です