3のべき乗の2進数表現全体は正規表現で書ける?

質問

オートマトン理論の本の練習問題を解いていて以下のような疑問に行き当たりました。

アルファベット{0, 1}上の語を2進数とみなすとき、 2のべき数については
2のべき乗の2進数表現の全体　->　10*
4のべき乗の2進数表現の全体　->　1(00)*
8のべき乗の2進数表現の全体　->　1(000)*
...
というように正規表現で書くことができますが、「xのべき乗」のxが2のべき数以外のときにこのように正規表現で表せる場合は存在するのでしょうか?

とりあえずx=3や5で小さい方から20個程べき数を列挙し、それらを受理する有限オートマトンを作ろうとしたのですが、私の能力では出来ませんでした。そこで不可能であることを証明することに方針を変えたのですが、そちらもまだ出来ないでおります。

どなたかこの問題を御教示いただけないでしょうか。
どうぞよろしくお願いいたします。

回答No.3

Tacosan · ベストアンサー

すみません, #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のべきではありえません.

お礼

御教示どうもありがとうございます。いや～鮮やかなものですね。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は正則ではないことが言える。

回答No.4

Tacosan

そんな感じです.
もっと一般化すると
{0, 1, ..., p-1}上の語を p進数とみなしたときに「q のべきを表す正規表現」が存在するかどうか
が
log[p] q が有理数かどうか
で判定できる, と. p, q によっては「p のべきが q のべきで割り切れる」という状況が考えられるので, #3 のようにはいきません.

お礼

再三の御教示をありがとうございます。
基数を一般化するとまたいくらか(?)難しくなるわけですか。教えていただいたことをもとに自分なりの証明を考えてみたい思います。

回答No.2

Tacosan

たぶん, log[2] 3 (2 を底とする 3 の対数) が無理数であることを背景に Pumping Lemma.
実際には log[2] 3 は超越数ですが, この証明ではそこまでは要求しないと思います.

お礼

>log[2] 3 (2 を底とする 3 の対数) が無理数

なるほど!光明が見えた気がしました。
御教示どうもありがとうございました。

回答No.1

info22

>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*で表せる、といった具合ですね。