概率自動機

概率自動機(probabilistic automaton)亦稱隨機自動機一種自動機。是所處環境或內部具有有限或無限的隨機因素的自動機，與非概率型自動機的主要區別是：概率自動機的動作是隨機的。每個概率自動機一般都需規定兩組概率：一是給定自動機的初始狀態的概率分佈—初始分佈，一般用一個隨機矢量表示；二是規定在自動機處於某一狀態，並向自動機輸人某個字母的條件下，自動機下一動作(如狀態轉移、輸出某個字母、改寫字母等)的條件概率函數。有了這兩組概率，就可計算自動機到達某個最終狀態的概率。包含有不可靠元件的數字電路和通信的信道都可以表示為概率自動機。

概率自動機可以被定義為非確定性有限自動機（

，Σ，

，

，

）的擴展，以及兩個概率：發生特定狀態轉換的概率

，以及初始狀態

由隨機向量代替，給出自動機處於給定初始狀態的概率。

對於普通的非確定性有限自動機，人們有：

一組有限的狀態

。

一組有限的輸入符號Σ。

過渡函數

：

×Σ→

（

）。

一組狀態

區分為接受（或最終）狀態

⊂

。

這裏，

（

）表示

的冪集。

通過使用currying，非確定性有限自動機的轉移函數

：

×Σ→

（Q）可以寫成隸屬函數。

：

×Σ×

→{0,1}

因此，如果

'∈

（

，

），則

（

，

，

'）= 1，如果

'=

（

，

），則

（

，a，

'）= 0。 咖喱變換函數可以理解為具有矩陣條目的矩陣。

'=

（

，

，

'）

矩陣

然後是方陣，其條目為零或一，表示NFA是否允許轉換

→

'。總是為非確定性有限自動機定義這種轉移矩陣。

對於字母表Σ中的每個符號

，概率自動機用一系列隨機矩陣

替換這些矩陣，以便通過下式給出轉換的概率：

當然，從某個州到任何州的狀態變化必須以概率1發生，因此必須具有

對於所有輸入字母

和內部狀態

。概率自動機的初始狀態由行向量v給出，其組件加到1：

轉移矩陣作用於右側，因此在消耗輸入字符串a b c之後概率自動機的狀態將是

特別地，概率自動機的狀態總是隨機向量，因為任意兩個隨機矩陣的乘積是隨機矩陣，並且隨機向量和隨機矩陣的乘積也是隨機向量。這個向量有時被稱為狀態分佈，強調它是一個離散的概率分佈。

形式上，概率自動機的定義不需要非確定性自動機的機制，這可以省略。形式上，概率自動機被定義為元組（

，Σ，

，

，

）。拉賓自動機是初始分佈

是座標向量的自動機;也就是説，除了一個條目之外的所有條目都為零，其餘條目為1。

每種常規語言都是隨機的，更強烈的是，每種常規語言都是η-隨機的。 一個弱的反面是每個0隨機語言都是正則的; 然而，一般的反過來並不成立：有一些不規則的隨機語言。

每個η-隨機語言都是隨機的，對於某些0 <η<1。

每個隨機語言都可以由Rabin自動機代表。

如果η是一個孤立的切點，那麼Lη是一種常規語言。

概率自動機具有幾何解釋：狀態向量可以被理解為生活在標準單形的面上，與正交角相對的點。 轉換矩陣形成一個幺半羣，作用於這一點。 這可以通過使點來自一些一般拓撲空間來推廣，而過渡矩陣選自作用於拓撲空間的算子集合，從而形成半自動機。 當切點適當地推廣時，具有拓撲自動機 ^[1]  。

這種概括的一個例子是量子有限自動機; 這裏，自動機狀態由復射影空間中的點表示，而轉移矩陣是從單一組中選擇的固定集。 切點被理解為對量子角的最大值的限制。