

オートマトン理論の本の練習問題を解いていて以下のような疑問に行き当たりました。
アルファベット{0, 1}上の語を2進数とみなすとき、 2のべき数については
2のべき乗の2進数表現の全体 -> 10*
4のべき乗の2進数表現の全体 -> 1(00)*
8のべき乗の2進数表現の全体 -> 1(000)*
...
というように正規表現で書くことができますが、「xのべき乗」のxが2のべき数以外のときにこのように正規表現で表せる場合は存在するのでしょうか?
とりあえずx=3や5で小さい方から20個程べき数を列挙し、それらを受理する有限オートマトンを作ろうとしたのですが、私の能力では出来ませんでした。そこで不可能であることを証明することに方針を変えたのですが、そちらもまだ出来ないでおります。
どなたかこの問題を御教示いただけないでしょうか。
どうぞよろしくお願いいたします。
No.3ベストアンサー
- 回答日時:
すみません, #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
- 回答日時:
そんな感じです.
もっと一般化すると
{0, 1, ..., p-1}上の語を p進数とみなしたときに「q のべきを表す正規表現」が存在するかどうか
が
log[p] q が有理数かどうか
で判定できる, と. p, q によっては「p のべきが q のべきで割り切れる」という状況が考えられるので, #3 のようにはいきません.
再三の御教示をありがとうございます。
基数を一般化するとまたいくらか(?)難しくなるわけですか。教えていただいたことをもとに自分なりの証明を考えてみたい思います。
No.1
- 回答日時:
>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が1つ増える)、よってxのべき乗のx進数表現全体は正規表現10*で表せる、といった具合ですね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10の0.3乗って??
-
logeの計算
-
常用対数についての問題です。7...
-
なぜ高速フーリエ変換はO(n*log...
-
アルキメデス螺旋に等間隔点列...
-
情報通信の、
-
262144って2の何乗でしょうか?
-
∮x ^2/x-1 dxの計算結果につい...
-
ログを使う計算式をエクセルで...
-
1/2+1/4+1/6+……+1/(2n)が発散
-
小学生の問題です
-
1000分の3は何%ですか
-
付き合った日を1日から数える...
-
1/300から1/500への縮尺の寸法...
-
1000円の3割の計算教えて下さい
-
0.5時間などの時間計算の方法
-
ExcelでLog10を自然数に直すには
-
エクセルの関数 ENTERを...
-
1/2÷1/2はなぜ1になるのか?
-
計算結果の微妙なズレ(大学入試)
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
logeの計算
-
10の0.3乗って??
-
2の50乗を簡単に概算出来る方...
-
乗数計算がわかりません
-
∮x ^2/x-1 dxの計算結果につい...
-
【経済】毎年3%ずつ成長率が上...
-
log(-2)の求め方
-
262144って2の何乗でしょうか?
-
常用対数についての問題です。7...
-
平均情報量を求める問題ですが...
-
真数の真という漢字にはどのよ...
-
ログを使う計算式をエクセルで...
-
小数点以下の乗倍数について。
-
数学の極限の問題です! (1)l...
-
画像、見難くてすみません。 ま...
-
木の高さを調べる方法
-
累乗指数計算
-
31の31乗を計算したい
-
log20/0.14=21.391.. となりま...
-
∫[2、∞] dx/logx の発散・収束...
おすすめ情報