自己共役なオートマトン。

有限オートマトンの簡単な例題で遊んでいるうちに浮かんだ着想を書き記しておく。

ある有限オートマトンがあるとき，それを開始状態と受理状態がいずれもひとつだけであるような一般化有限オートマトン（一般化というよりも，ある種の基準を満たすように規格化されたものなので，正規化オートマトンもしくは正則オートマトンなどと呼ぶのが相応しいように思う）の開始状態を受理状態に，受理状態を開始状態に取り換え，状態遷移の矢印をすべて逆向きに書き換えたものを，もとのオートマトンの共役と呼ぶことにする。いわばオートマトンを逆回しに動かすことに相当するので，逆オートマトンと呼ぶ方がしっくりくるかもしれないが。

オートマトンの中には共役オートマトンの受理言語が元のオートマトンと一致するものがあるが，そのようなオートマトンを自己共役であるということにするというのはどうだろうか。このような用語が何かの役に立つのであれば，すでに誰かが似たような名前を付けていることであろう。

自己共役なオートマトンの受理言語は，きちんと証明したわけではないが，たぶん鏡像変換に対して不変な「回文」になっているはずである。

正規表現の簡略化について。

2状態のみからなる簡単な決定性有限オートマトン DFA が受理する語の正規表現を求めるため，新たな開始状態と受理状態を追加して一般化非決定性有限オートマトン GNFA に書き換え，状態遷移図において遷移を表す矢印に付したラベルを書き換えながら状態を一つずつ減らしていくアルゴリズムに従って最終的な正規表現を得るという手続きを理解した。その際，どの状態から消去するかに伴い，二通りの正規表現が得られる。それらは同じ文字列の集合を表す等価な表現のはずだが，それらが実際に等価であることをいかに照明するのか，それが現在の悩みの種である。

ここでいう正規表現とは，文字列 x と y に対し，

x と y をこの順番に並べて新しい語 xy を作り出す接合と，

x または y のいずれかを選んで並べる選択 x∪y，

そして同じ語を 0 回以上繰り返して並べたものの全体を表す反復 x*（0 回の繰り返しに関しては省略可能な空文字εを表すと定める）

の三種類である。これらの他，文字列 x を構成する文字を逆順に並べた鏡像 xR を対応させる写像も含めるのだったかどうか，記憶があやふやである。
まｔ
ともかく，以上の設定のもとで，ごくごく当たり前の以下の書き換え規則を見出した。これら以外にも基本的な規則があるに違いないが，さしてシステマティックに調べていない。なお，上記の演算規則の強さについては，反復（累乗）* を最優先し，その次に接合，最後に選択ということにする。また，二つの正規表現 REX1 と REX2 が表す集合が等しいことを REX1=REX2 のように表すこととする。

(1) 吸収

(x∪y)* は x または y を並べてできるあらゆる文字列の集合であるから、

x*(x∪y)*=(x∪y)*x*=x∪(x∪y)*=(x∪y)*∪x=(x∪y)*

が成り立つ。

(2) 交換則

文字 a のべきのみからなる二つの文字列 x, y について xy=yx が成り立つ。

(3) 分割

x* は x を一つも並べない空文字か，x を一つ以上並べた文字列のいずれかであるから，

x*=ε∪xx*

が成り立つ。このことから，

x*y=y∪xx*y,
yx*=y∪yx*

などが成り立つ。


僕が気づいた規則は今のところこれだけであるが，(1) と (3) は正規表現の簡約化に役立ちそうである。

二つの正規表現が等価であることを湿すには，素直かつ自然な方法として数学的帰納法による証明が考えられるが，そのような方法以外に等価であるかどうかを判定する簡便なやり方があるのか，興味のあるところである。

一段落。

相変わらず気温は冬の水準であるとはいえ，昨日今日と昼間の風に春の香りを嗅いだ気がした。

1月3日から取り組んできたレポート課題10題は昨日のうちに全て解答のめどがついた。予定通り，この週末にまとめる準備は整った。

あとは，そう，ホントにちゃんとまとめるかどうか，それが我ながら気がかりではあるが，まあ，明日から少しずつ取り組もうと思う。