- ベストアンサー
3のべき乗の2進数表現全体は正規表現で書ける?
- 2のべき数については正規表現で表せるが、2のべき数以外の場合は存在するか疑問がある
- x=3や5で小さい方から20個程べき数を列挙し、受理する有限オートマトンを作ったがうまくいかなかった
- この問題について教えていただける方を求めています
- 数学・算数
- 回答数4
- ありがとう数5
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
すみません, #2 ははずしています. もっと簡単に行けます(たぶん). 以下は証明の概略: {0, 1}上の語 w に対し w が表す 2進数を N(w), ビット数を |w| で表すことにします. 「3のべきを表す正規表現」が存在すると仮定すると, Pumping Lemma から「uv^iw (i ≧ 1 かつ |v| ≧ 1) が全て 3のべきであるような u, v, w」が存在します. そこで N(uvw) = 3^m, N(uv^2w) = 3^n とおきます. すると N(uv^3w) = 3^n + (3^n-3^m)2^|v| と書けますが, この右辺は 3^n で割り切れず, したがって 3のべきではありえません.
その他の回答 (3)
- Tacosan
- ベストアンサー率23% (3656/15482)
そんな感じです. もっと一般化すると {0, 1, ..., p-1}上の語を p進数とみなしたときに「q のべきを表す正規表現」が存在するかどうか が log[p] q が有理数かどうか で判定できる, と. p, q によっては「p のべきが q のべきで割り切れる」という状況が考えられるので, #3 のようにはいきません.
お礼
再三の御教示をありがとうございます。 基数を一般化するとまたいくらか(?)難しくなるわけですか。教えていただいたことをもとに自分なりの証明を考えてみたい思います。
- Tacosan
- ベストアンサー率23% (3656/15482)
たぶん, log[2] 3 (2 を底とする 3 の対数) が無理数であることを背景に Pumping Lemma. 実際には log[2] 3 は超越数ですが, この証明ではそこまでは要求しないと思います.
お礼
>log[2] 3 (2 を底とする 3 の対数) が無理数 なるほど!光明が見えた気がしました。 御教示どうもありがとうございました。
- info22
- ベストアンサー率55% (2225/4034)
>3のべき乗の2進数表現全体は正規表現で書ける? 3,3^2,3^3など簡単な例ならやれるでしょうからやってみてください。 ダメなこと位すぐ分かりませんか？ なので、全体でも書けないといえますね！ 3のべき乗の3進数表現全体は正規表現や 9のべき乗の3進数表現全体は正規表現や 27のべき乗の3進数表現全体は正規表現 ... なら書けるでしょう。 一般に xのべき乗のx進数表現全体は正規表現や x^2のべき乗のx進数表現全体は正規表現や x^3のべき乗のx進数表現全体は正規表現 ... なら書けるでしょう。
お礼
御投稿ありがとうございます。 >ダメなこと位すぐ分かりませんか？ >なので、全体でも書けないといえますね！ 3のべき乗の2進数表現全体を正規表現で書く(あるいはそれを受理する有限オートマトンを作る)ことは出来ない、ということでしょうか。私の予想もそうなのですが、だとするとそれはどのように証明すればいいのでしょうか。 >一般に >xのべき乗のx進数表現全体は正規表現や >x^2のべき乗のx進数表現全体は正規表現や >x^3のべき乗のx進数表現全体は正規表現 >... >なら書けるでしょう。 xの0乗(のx進表現)=1、x倍する=x進で1桁上がる(0が１つ増える)、よってxのべき乗のx進数表現全体は正規表現10*で表せる、といった具合ですね。
お礼
御教示どうもありがとうございます。いや～鮮やかなものですね。2進でx桁多い(0詰め)=10進で2^|x|倍、というテクニックは是非身につけなければと思いました。この度は本当にありがとうございました。 (以下は私なりに若干の補足をさせていただいたものです。3のべき数をxのべき数に一般化したものへも容易に拡張できそうですね) ---- {0,1}上の言語Lp3={3のべき数の2進数表現の全体}が正則であるとし、語zをLp3の元とする。すると反復補題からuv^iw(i=0,1,2...)も やはりLp3の元となるようなzの分割z=uvw(|v|>=1)が存在する。 ここでzの10進での値をN(z)で表すとして、N(z)=3^mであるとする。すると、y=uv^2w=uvvwもLP3の元であることからN(y)=3^nと表せ、yの方がzより桁数が大きいことからyはzで割り切れる(N(y)/N(z)=3^{n-m}においてn-mは正整数)。 次にx=uv^3w=uvvvwを考えると、 N(x)-N(y)=N(uv-v)・2^|vvw| および N(y)-N(z)=N(uv-v)・2^|vw| より、xの10進での値は N(x) =N(y)+N(uv-v)・2^|vvw| =N(y)+(N(y)-N(z))・2^|v| =3^n+(3^n-3^m)・2^|v| となる。 ここでxもLp3の元、すなわちN(x)=3^lであるならば、xの方がyより桁数が大きいことからN(x)=3^n+(3^n-3^m)・2^|v|はN(y)=3^nで割り切れるはずである。 ところが、右辺を3^nで割った商 (3^n+(3^n-3^m)・2^|v|)/3^n=1+2^|v|-3^{m-n}・2^|v| において、最後の項3^{m-n}・2^|v|は整数とはなりえない(なぜなら3^{m-n}・2^|v|=s(sは正整数)であるとすると2^|v|=s・3^{n-m}と変形できるが、左辺の素因数が2だけなのに対して右辺の素因数に3が含まれており矛盾)。よって商全体1+2^|v|-3^{m-n}・2^|v|も整数とはならず、xはLp3の元ではない。 以上から冒頭に述べたような分割は存在せず、Lp3は正則ではないことが言える。