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