オートマトン理論の本の練習問題を解いていて以下のような疑問に行き当たりました。
アルファベット{0, 1}上の語を2進数とみなすとき、 2のべき数については
2のべき乗の2進数表現の全体 -> 10*
4のべき乗の2進数表現の全体 -> 1(00)*
8のべき乗の2進数表現の全体 -> 1(000)*
...
というように正規表現で書くことができますが、「xのべき乗」のxが2のべき数以外のときにこのように正規表現で表せる場合は存在するのでしょうか?
とりあえずx=3や5で小さい方から20個程べき数を列挙し、それらを受理する有限オートマトンを作ろうとしたのですが、私の能力では出来ませんでした。そこで不可能であることを証明することに方針を変えたのですが、そちらもまだ出来ないでおります。
どなたかこの問題を御教示いただけないでしょうか。
どうぞよろしくお願いいたします。
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*で表せる、といった具合ですね。
No.2
- 回答日時:
たぶん, log[2] 3 (2 を底とする 3 の対数) が無理数であることを背景に Pumping Lemma.
実際には log[2] 3 は超越数ですが, この証明ではそこまでは要求しないと思います.
>log[2] 3 (2 を底とする 3 の対数) が無理数
なるほど!光明が見えた気がしました。
御教示どうもありがとうございました。
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 のようにはいきません.
再三の御教示をありがとうございます。
基数を一般化するとまたいくらか(?)難しくなるわけですか。教えていただいたことをもとに自分なりの証明を考えてみたい思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 数学 正規数の定義で分からないことがあります。 正規数の定義について専門書において 「xがr進正規であると 1 2023/07/17 20:50
- その他(コンピューター・テクノロジー) 量子コンピュータの動作原理がわかりません。同じビットが、1でも0でも有って良いだろうか? 3 2023/02/04 03:20
- 統計学 t統計量とF統計量について 9 2023/01/05 14:23
- 英語 口頭での"the following..."の可否等について 6 2022/08/19 01:01
- 政治 中国は一票の格差4倍で、日本は3倍ですが、それでも日本は民主主義国なら中国も同じですよね? 2 2023/03/16 04:52
- その他(形式科学) 非決定性有限オートマトンの問題について 1 2022/07/21 21:10
- 数学 これって正しいんじゃないの? 「無理数を小数で表現すると、小数点以下に数字が無限に続きますが、それら 5 2022/05/29 23:56
- その他(データベース) 4進数風なバーコードは何ですか? 2 2022/11/28 23:33
- その他(コンピューター・テクノロジー) 正規表現の置換で数値を合計したいです。 2 2022/10/17 11:01
- 数学 大学数学 「条件:t進表現において、何乗しても右から2桁が変わらない2桁の自然数が存在する。」 上記 7 2023/06/28 22:25
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
logeの計算
-
10の0.3乗って??
-
2の50乗を簡単に概算出来る方...
-
2のN乗が10の場合、手計算で...
-
得点率について
-
1/2+1/4+1/6+……+1/(2n)が発散
-
262144って2の何乗でしょうか?
-
【経済】毎年3%ずつ成長率が上...
-
分数の場合のlogの計算の仕方が...
-
log(-2)の求め方
-
物理の計算で×10^3とかするのは...
-
べき乗とはなんでしょうか? 数...
-
∮x ^2/x-1 dxの計算結果につい...
-
常用対数についての問題です。7...
-
√(55000/n)が整数になるとき...
-
小数点以下の乗倍数について。
-
数学の口頭試問具体例を教えて...
-
乗数計算がわかりません
-
2を何乗したら2億を超えるか
-
情報エントロピーの一様分布の...
おすすめ情報