世界線航跡蔵

Mad web programmerのYuguiが技術ネタや日々のあれこれをお送りします。

2004年05月31日

Thue-Morse語

aを種として 次の規則により生成される無限語をThue-Morse語という。

  • a |→ ab
  • b |→ ba

これは、単純なオートマトンによっても生成される。オートマトンM=(a, I, S, δ, H)を次のように定義する。

初期状態
a
入力文字集合
I = {0,1}
状態集合
S = {a,b}
遷移関数
δ(a,0)=a, δ(b,0)=b, δ(a,1)=b, δ(b,1)=a
終了状態集合
H=ø

また、自然数nの2進数表示 ∈ I* を与える写像f: N → I* を考える。ただしf(0) は空語 λ とする。このとき状態列 δ(a, f(0)), δ(a, f(1)), δ(a, f(2)), ... はThue-Morse語である。

そっかー。こんな単純なところでThue-Morse語がでてくるわけか。そして、Thue-Morse語で定義される実数が再びβ展開のところで活躍すると。これはある意味で双対になってる? もう少し構造を調べないとわからないけど、でも美しい。

今日の講義は最高だった。

トラックバック

http://yugui.jp/articles/96/ping

現在のところトラックバックはありません

コメント

blog comments powered by Disqus

ご案内

前の記事
次の記事

タグ一覧

過去ログ

  1. 2016年07月
  2. 2016年01月
  3. 2015年09月
  4. 2015年08月
  5. 過去ログ一覧

フィード

フィードとは

その他

Powered by "rhianolethe" the blog system