確率オートマトン

数学とコンピュータサイエンスにおいて、確率オートマトン（PA ）は非決定性有限オートマトンを一般化したものである。PAは与えられた遷移の確率を遷移関数に含め、遷移行列に変換する。^{[1] [2]したがって、確率オートマトンはまた、}マルコフ連鎖と有限型のサブシフトの概念を一般化している。確率オートマトンによって認識される言語は確率言語と呼ばれ、これには正規言語がサブセットとして含まれる。確率言語の数は無数である。

この概念は1963年にマイケル・O・ラビンによって導入されました。 ^[2]特定の特殊なケースはラビンオートマトンと呼ばれることもあります（ラビンオートマトンとも呼ばれるωオートマトンの一種と混同しないでください）。近年、量子確率の観点からその変種である量子有限オートマトンが定式化されました。

与えられた初期状態と入力文字に対して、決定性有限オートマトン(DFA) は次の状態を 1 つだけ持ち、非決定性有限オートマトン(NFA) は次の状態のセットを持ちます。確率オートマトン (PA) は、代わりに次の状態の重み付きセット (またはベクトル) を持ちます。ここで、重みの合計は 1 になる必要があり、したがって確率として解釈できます (確率ベクトルになります)。状態と受け入れの概念も、これらの重みの導入を反映するように変更する必要があります。与えられたステップとしてのマシンの状態は、状態の確率ベクトルと、受け入れ状態にある合計確率が何らかのカットオフを超えた場合に受け入れられる状態によっても表される必要があります。

PA は、次の状態のセットを許可しながらも、その重みに制限があるため、ある意味では決定論的から非決定論的への中間ステップです。ただし、これは多少誤解を招きます。PA は重みを定義するために実数の概念を利用しています。これは、DFA と NFA の両方の定義には存在しません。この追加の自由により、無理数パラメータを持つ p 進言語など、正規ではない言語を決定できます。そのため、PA は DFA と NFA (どちらも同等に強力であることは有名です) の両方よりも強力です。

確率オートマトンとは、非決定性有限オートマトン を拡張したもので、特定の状態遷移が発生する確率と、初期状態を、オートマトンが特定の初期状態にある確率を示す確率ベクトルに置き換えた2 つの確率を伴って定義されます。 ${\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}$${\displaystyle P}$${\displaystyle q_{0}}$

通常の非決定性有限オートマトンの場合、

• 有限の状態集合${\displaystyle Q}$
• 入力シンボルの有限集合 ${\displaystyle \Sigma }$
• 遷移関数${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$
• 受け入れ状態（または最終状態）として区別される一連の状態。${\displaystyle F}$ ${\displaystyle F\subseteq Q}$

ここで、は の冪集合を表します。 ${\displaystyle \wp (Q)}$${\displaystyle Q}$

カリー化を使用することで、非決定性有限オートマトン遷移関数はメンバーシップ関数として記述できる。${\displaystyle \delta :Q\times \Sigma \to \wp (Q)}$

${\displaystyle \delta :Q\times \Sigma \times Q\to \{0,1\}}$

となる。カリー化された遷移関数は、行列要素を持つ行列として理解できる。 ${\displaystyle \delta (q,a,q^{\prime })=1}$${\displaystyle q^{\prime }\in \delta (q,a)}$${\displaystyle 0}$

${\displaystyle \left[\theta _{a}\right]_{qq^{\prime }}=\delta (q,a,q^{\prime })}$

行列は正方行列であり、そのエントリは 0 または 1 で、NFA によって遷移が許可されるかどうかを示します。このような遷移行列は、非決定性有限オートマトンに対して常に定義されます。 ${\displaystyle \theta_{a}}$${\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$

確率オートマトンでは、これらの行列をアルファベットの各記号aに対して、遷移の確率が次のように与えられる 右確率行列 の族に置き換えます。${\displaystyle P_{a}}$${\displaystyle \Sigma }$

${\displaystyle \left[P_{a}\right]_{qq^{\prime }}}$

もちろん、ある状態から任意の状態への状態変化は確率1で起こるはずなので、

${\displaystyle \sum _{q^{\prime }}\left[P_{a}\right]_{qq^{\prime }}=1}$

すべての入力文字と内部状態に対して、確率オートマトンの初期状態は行ベクトルで与えられ、その要素は個々の初期状態の確率であり、その合計は1になります。 ${\displaystyle a}$${\displaystyle q}$ ${\displaystyle v}$${\displaystyle q}$

${\displaystyle \sum _{q}\left[v\right]_{q}=1}$

遷移行列は右側に作用するので、確率オートマトンが入力文字列を消費した後の状態は次のようになる。 ${\displaystyle abc}$

${\displaystyle vP_{a}P_{b}P_{c}}$

特に、確率オートマトンの状態は常に確率ベクトルです。これは、任意の 2 つの確率行列の積が確率行列であり、確率ベクトルと確率行列の積も確率ベクトルであるためです。このベクトルは、離散確率分布であることを強調して、状態の分布と呼ばれることもあります。

正式には、確率オートマトンの定義には非決定性オートマトンの構造は必要ないため、省略できます。正式には、確率オートマトンPAはタプル として定義されます。Rabinオートマトンとは、初期分布が座標ベクトル であるオートマトンです。つまり、1 つのエントリを除くすべてのエントリが 0 で、残りのエントリが 1 です。 ${\displaystyle (Q,\Sigma ,P,v,F)}$${\displaystyle v}$

確率オートマトンによって認識される言語の集合は確率言語と呼ばれます。これには正規言語がサブセットとして含まれます。

をオートマトンが「受け入れる」または「最終的な」状態の集合とします。表記法の乱用により、 はのメンバーシップ関数である列ベクトルであるとも理解できます。つまり、 の要素に対応する場所では 1 を持ち 、それ以外の場所では 0 を持ちます。このベクトルは、内部状態確率と縮約してスカラー を形成することができます。特定のオートマトンによって認識される言語は、次のように定義されます。 ${\displaystyle F=Q_{\text{accept}}\subseteq Q}$${\displaystyle Q_{\text{受け入れる}}}$${\displaystyle Q_{\text{受け入れる}}}$${\displaystyle Q_{\text{受け入れる}}}$

${\displaystyle L_{\eta }=\{s\in \Sigma ^{*}\vert vP_{s}Q_{\text{accept}}>\eta \}}$

ここで、 はアルファベットのすべての文字列の集合です（したがって、 * はクリーネの星です）。言語はカットポイントの値に依存し、通常は の範囲内にあるとされます。 ${\displaystyle \Sigma^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \eta}$${\displaystyle 0\leq \eta <1}$

言語がη -確率的であると言われるのは、固定された に対して、その言語を認識する何らかの PA が存在する場合のみです。言語が確率的であると言われるのは、 に対してη -確率的である何らかのPA が存在する場合のみです 。 ${\displaystyle \eta}$${\displaystyle 0\leq \eta <1}$${\displaystyle L_{\eta}}$

カットポイントが孤立カットポイントであるとは、次のようなものが存在する場合のみである。 ${\displaystyle \delta >0}$

${\displaystyle \vert vP(s)Q_{\text{accept}}-\eta \vert \geq \delta }$

全ての${\displaystyle s\in \Sigma ^{*}}$

すべての正規言語は確率的であり、より強い意味では、すべての正規言語は η確率的です。弱い逆は、すべての 0 確率言語が正規であるということです。ただし、一般的な逆は成り立ちません。つまり、正規ではない確率言語が存在します。

すべてのη -確率言語は、ある に対して確率的です。 ${\displaystyle 0<\eta <1}$

すべての確率言語は、ラビンオートマトンによって表現できます。

が孤立したカットポイントである場合、 は正規言語です。 ${\displaystyle \eta}$${\displaystyle L_{\eta}}$

p進言語は、非正規な確率言語の例であり、確率言語の数が無数であることも示している。p進言語は、文字列の集合として定義される 。

${\displaystyle L_{\eta }(p)=\{n_{1}n_{2}n_{3}\ldots \vert 0\leq n_{k}}p{\text{ かつ }}0.n_{1}n_{2}n_{3}\ldots >\eta \}}$

文字の中に。 ${\displaystyle 0,1,2,\ldots ,(p-1)}$

つまり、p進言語は、単にp を底として表され、 より大きい[0, 1] 内の実数の集合です。すべてのp進言語が確率的であることは簡単に示せます。 ^[3]特に、これは確率言語の数が無数であることを意味します。p進言語が正則であるためには、が有理数である必要があります。 ${\displaystyle \eta}$${\displaystyle \eta}$

確率オートマトンには幾何学的な解釈があります。つまり、状態ベクトルは、直交コーナーの反対側にある標準単体の面上にある点であると理解できます。遷移行列はモノイドを形成し、点に作用します。これは、点を何らかの一般的な位相空間から取得し、遷移行列を位相空間に作用する演算子のコレクションから選択することで一般化できます。これにより、半オートマトンが形成されます。カットポイントが適切に一般化されると、位相オートマトンが得られます。

このような一般化の一例は量子有限オートマトンである。ここでは、オートマトンの状態は複素射影空間内の点として表され、遷移行列はユニタリ群から選択された固定集合である。カットポイントは量子角の最大値の限界として理解される。

• Salomaa, Arto (1969)。「有限非決定性および確率的オートマトン」。オートマトン理論。オックスフォード:ペルガモン プレス。