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語で定義される実数が再びβ展開のところで活躍すると。これはある意味で双対になってる? もう少し構造を調べないとわからないけど、でも美しい。

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