有限オートマトンとの関係

ウィキペディア小見出し辞書

有限オートマトンとの関係

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/05 08:02 UTC 版)

「正規数」の記事における「有限オートマトンとの関係」の解説

Agafonov (1968) は有限オートマトンと正規列との関係を指摘した。正規列からある正則言語によって得る部分列はまた正規列である。言い換えると、正規列を有限オートマトンに入力し、受理状態のときのみ入力した文字をそのまま出力することにすれば、そうして出力される部分列はまた正規である。 以下の二つの事実が示すように、正規列と有限オートマトンとの間にはより深い関係がある。 有限状態ギャンブラー（finite-state gambler または finite-state martingale、以下 FSG）とは、有限アルファベット Σ 上の有限オートマトンの状態に応じて文字たち（Σ の各元）に金を賭けるギャンブラーのモデルのことである。例えばバイナリアルファベット Σ = { 0, 1 } 上の FSG は、現在の状態 q に対して定められた割合 q0 (0 ≤ q0 ≤ 1), q1 (= 1 - q0) に従い、ギャンブラーは持ち金の q0 倍を 0 に賭け、残りを 1 に賭ける。それから文字が入力され、その文字に賭けられた金の2倍（一般には |Σ| 倍）が次の賭けの元手となる。入力された文字に従い、有限オートマトンの状態が移り、ギャンブラーの賭け方が変わる。ある FSG d が無限列 S に対して成功するとは、有限の元手から始めていつかは任意の目標額に到達すること、すなわち lim sup n → ∞ d ( S ↾ n ) = ∞ が成り立つことをいう。ここに、 d ( S ↾ n ) はギャンブラー d が S の最初の n 個の文字を読み込んだときに持っている金額を表し、limsup は上極限を意味する。 Schnorr, Stimm (1972) は、正規列に対して「成功する」FSG は存在しないことを示し、Bourke, Hitchcock, Vinodchandran (2005) はその逆を示した。すなわち、 文字列が正規であることと、その列に対して「成功する」FSG が存在しないことは同値である ことが知られている。 有限状態圧縮機 (finite-state compressor) とは、有限オートマトンの状態に応じて文字列（空列もあり得る）を出力する機械のモデルである。有限状態可逆圧縮機（information lossless finite-state compressor、以下 ILFSC）とは、出力データおよび最終状態から入力データを一意に復元できる有限状態圧縮機のことである。言い換えると、アルファベット Σ 上の有限状態圧縮機 C の状態集合が Q であるとき、C が ILFSC であるとは、C に入力したデータを出力データと最終状態のペアに移す写像 f : Σ* → Σ* × Q が全単射であることを言う。ハフマン符号やシャノン符号といった圧縮の技術は ILFSC を用いて実装することができる。ある ILFSC C が無限列 S を圧縮するとは、 lim inf n → ∞ C ( S ↾ n ) n < 1 が成り立つことをいう。ここに、 C ( S ↾ n ) はC が S の最初の n 個の文字を読み込んだときに出力した文字の個数を表し、liminf は下極限を意味する。 Ziv, Lempel (1978) は 文字列が正規であることと、その列を「圧縮する」ILFSC が存在しないことは同値である ことを示した。実際には彼らは次の事実を示している。「ある文字列の ILFSC による最適な圧縮率は、その列のエントロピー率（entropy rate、エントロピーのビット数に対する比）に等しい。」エントロピー率は、ある意味で正規であることにどれだけ近いかを表す数値であり、正規である場合は丁度 1 になる（入力した文字をそのまま出力する ILFSC では、圧縮率が 1 であることも注意しておく）。LZ 圧縮アルゴリズムは漸近的に任意の ILFSC 以上の圧縮率を誇るため、任意の非正規列を圧縮することができる。 この二つの正規列の特徴付けを標語的にまとめると、正規であることは有限オートマトンで制御できない程「ランダム」である、と言える。同様に、チューリングマシンに対して「ランダム」であるという概念を考えることができる。理論的にチューリングマシンは有限オートマトンよりも高性能であるため、この概念は正規であるという概念よりも強い。