確率オートマトン

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

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

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

パワーアンプ（PA）は、ある意味では決定論的から非決定論的への中間段階と言えます。なぜなら、PAは一連の次の状態を許容するものの、その重みには制約があるからです。しかし、これはやや誤解を招く表現です。PAは重みを定義するために実数の概念を利用しますが、これは決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）の定義には見られない概念です。この自由度の高さにより、PAは非正規言語、例えば無理数パラメータを持つp進言語なども判定できるようになります。そのため、PAはDFAとNFA（両者の能力は同等）よりも強力です。

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

通常の非決定性有限オートマトンでは、次のようになる。

• 有限個の状態${\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 })}$

マトリックス$\displaystyle \theta _{a}}$これは正方行列であり、その要素はゼロまたはイチで、遷移が起こったかどうかを示します。$\displaystyle q{\stackrel {a}{\rightarrow }}q^{\prime }}$これはNFAによって許可されています。このような遷移行列は、非決定性有限オートマトンに対して常に定義されます。

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

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

ある状態から任意の状態への状態変化は、当然ながら確率1で発生しなければならず、したがって、

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

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

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

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

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

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

形式的には、確率オートマトンの定義には非決定性オートマトンの動作原理は必要なく、省略してもよい。形式的には、確率オートマトンPAはタプルとして定義される。${\displaystyle (Q,\Sigma ,P,v,F)}$ラビンオートマトンとは、初期分布が${\displaystyle v}$は座標ベクトルです。つまり、1つの要素を除いてすべてゼロであり、残りの1つの要素は1です。

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

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

${\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 が存在する場合に限る。${\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進言語とは、[0, 1] の実数をp基数で表した集合であり、以下の値以上である。${\displaystyle \eta }$すべてのp進言語が確率的であることを示すのは簡単である。 ^{[ 3 ]}特に、これは確率的言語の数が非可算であることを意味する。p進言語が正則であるのは、次の場合に限る。${\displaystyle \eta }$合理的である。

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

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

• 重み付きオートマトン

• Salomaa, Arto (1969). 「有限非決定性および確率的オートマタ」.オートマタ理論. オックスフォード: Pergamon Press .