機率自動機

在數學和計算機科學中，機率自動機(Probabilistic Automaton，PA)是非確定性有限自動機的推廣; 它包括給定轉換到轉換函式的機率，將其轉換為轉換矩陣。 因此，機率自動機概括了馬爾可夫鏈或有限類型的子移位的概念。 機率自動機識別的語言稱為隨機語言; 這些包括常規語言作為子集。 隨機語言的數量是不可數的。

基本介紹

• 中文名：機率自動機
• 外文名：probabilistic automaton
• 縮寫：PA

介紹

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

定義

機率自動機可以被定義為非確定性有限自動機（ ，Σ， ， ， ）的擴展，以及兩個機率：發生特定狀態轉換的機率 ，以及初始狀態 由隨機向量代替，給出自動機處於給定初始狀態的機率。

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

一組有限的狀態 。

一組有限的輸入符號Σ。

過渡函式 ： ×Σ→ （ ）。

一組狀態 區分為接受（或最終）狀態 ⊂ 。

這裡， （ ）表示 的冪集。

通過使用currying，非確定性有限自動機的轉移函式 ： ×Σ→ （Q）可以寫成隸屬函式。

： ×Σ× →{0,1}

因此，如果 '∈ （ ， ），則（ ， ， '）= 1，如果'= （ ， ），則 （ ，a， '）= 0。 咖喱變換函式可以理解為具有矩陣條目的矩陣。

'= （ ， ， '）

矩陣 然後是方陣，其條目為零或一，表示NFA是否允許轉換 → '。總是為非確定性有限自動機定義這種轉移矩陣。

對於字母表Σ中的每個符號 ，機率自動機用一系列隨機矩陣 替換這些矩陣，以便通過下式給出轉換的機率：

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

對於所有輸入字母 和內部狀態。機率自動機的初始狀態由行向量v給出，其組件加到1：

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

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

形式上，機率自動機的定義不需要非確定性自動機的機制，這可以省略。形式上，機率自動機被定義為元組（，Σ，，，）。拉賓自動機是初始分布是坐標向量的自動機;也就是說，除了一個條目之外的所有條目都為零，其餘條目為1。

屬性

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

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

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

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

推廣

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

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