Diary?

(22:35)

また檜山さんのところで面白そうな話が出てる。

• 状態遷移機械と非決定性遷移
• 未定義な遷移の解釈 -- 3つの立場

俺はとにかくコードを書いて動かすタイプなので、脊髄反射で書いてみた。言語は当然 Python。

def down(n):
  u = Undef(n)
  return u - 1
 
def up(n):
  return n + 1
 
def reset(n):
  return 0
 
class Undef(int):
  def __init__(self, n):
    int.__init__(self, n)
 
  def __add__(self, n):
    if self >= -1:
      return int(self)  + 1
    else:
      return Undef(int(self) + 1)
  
  def __sub__(self, n):
    if self > 0:
      return int(self)  - 1
    else:
      return Undef(int(self) - 1)
 
  def __str__(self):
    if self >= 0:
      return str(self)
    else:
      return 'undef(%d)' % (self)

一応これで

• up は 1 インクリメント
• down は 1 デクリメント、 0 への down の結果は未定義
• reset は 0 にする

という仕様を満たしているはず。 0 への down が未定義でも、 up(down(0)) と処理した結果は 0 に戻っていてもバチは当たるまい、むしろ自然じゃないかなと考えたのでこうした。とりあえず実行結果は以下のとおり。

>>> funcs = [up, up, reset, up, down, down, down ,up, up, up]
>>> n = 1
>>> for f in funcs:
...   n = f(n)
...   print n
2
3
0
1
0
undef(-1)
undef(-2)
undef(-1)
0
1

この未定義な状態というか非決定性が何の訳に立つかというと、例えば構文解析とか正規表現の類では活用出来るよね。例えば次のような Wiki 文法のパースなんかではもろに非決定的な状態遷移が出てくる。

見出し
======
 
パラグラフ
 
+リスト1
+リスト2
  リスト2 の続き
 +ネストしたリスト
  +さらなるネスト
+リスト 3
 
パラグラフ

これをパースするには「空行で区切る」「連続した空行で区切る」の二つがあるけど、後者は実際に使ってみたらソースコードの埋め込みとかで問題が起こるのであまり実用的ではなく、必然的に前者になる (どーでもいいけど、この日記の出力が時々おかしいのは後者のアルゴリズムで日記の記法をパースしてるせいで入力に制限があるから。とっとと直さないといけないんだけど、面倒につき絶賛放置中)。

一行ずつ読み込むと当然それだけではパラグラフなのか見出しなのかとかがまったく判断できないので、「次にくる物によって決定」せざるを得ないわけ。こういうのを非決定性有限オートマトンと呼び、正規表現のうち現在多くのアプリケーションで使われている NFA (Nondeterministic Finite Automaton) エンジンがその代表例だと思う (それに対するのは DFA)。実際には NFA をそのまま扱うのは効率面とかで問題があるらしく、その場合 DFA に変換して処理する (NFA -> DFA の変換アルゴリズムがある) らしいのだが詳しいことは知らん。

ところでこの状態遷移の話は前から書かれている圏論の話に繋がりそうな気がするけど、俺はそこまで頭良くないので具体的なことはわからん。