機率自動機論（probabilistic automata theory）自動機論的次級學科，主要研究所處環境或內部具有（有限或無限的）隨機因素的自動機。與非機率型自動機不同之處，是機率自動機的動作是隨機的。為了給定機率自動機，首先必需規定在自動機處於某一狀態，並向自動機輸入某個字母的條件下，自動機下一動作（如狀態轉移，輸出某個字母，改寫字母等）的條件機率函式。
基本介紹
- 中文名：機率自動機論
- 外文名：probabilistic automata theory
- 隸屬：自動機論
- 研究內容：所處環境或內部的隨機因素
發展簡況,主要內容,機率圖靈機,機率時序機,機率有限識別器,多階段判決過程,
發展簡況
早在40年代末，C.E.仙農在資訊理論的研究中，就提出了噪聲信道的數學模型(見圖[噪聲信道])，它實際上就是一種機率自動機。50年代初，J.諾伊曼研究用不可靠元件構造可靠機器，這個問題發展成為現代的容錯計算問題。但是直到50年代末，在R.W.阿西貝的著作中才給出一個形式定義的雛形。1963年M.O.拉賓比較嚴格地闡述了機率自動機的一些基本概念，並提出一些問題（如穩定性問題）。後來，A.帕茲等人的著作綜述了這一方面的研究成果。60年代末至70年代，有更多的人進行了這方面的研究工作。
主要內容
與一般的自動機理論相平行的，有機率圖靈機、機率時序機、機率識別器等方面的研究工作。這些工作一方面是推廣自動機已有的結果；另一方面也提出不少新的問題，豐富了自動機論的內容。
機率圖靈機
機率圖靈機是圖靈機的推廣。它的形式定義可以用六元組=(,,,,,)給出。其中和分別是非空有限的狀態集合和帶字母集合。和 分別是輸入字母集合和輸出字母集合，且∪，∩=。是初始分布(,|,)是已知機率圖靈機的狀態,且注視在帶字母 的條件下它的“下一動作”的機率。“下一動作”是下面三者之一。①[294-03]:用代替，且轉移到狀態；②=：讀寫頭向右移一單元,且轉移到狀態；③=：讀寫頭向左移一單元，且轉移到狀態。
在機率圖靈機的研究中，對可計算隨機函式，給出了定義並對可計算函式及其運算也都作了研究，而且還證明了圖靈機的許多研究結果在機率圖靈機的情況下仍然成立。函式代入、原始遞歸、求極小等運算對可計算隨機函式都是封閉的。限制在普通函式類的範圍內，可以證明部分可計算隨機函式中的普通函式，恰好是部分遞歸函式。從這個意義上看，把圖靈機推廣到機率圖靈機的計算能力沒有增大。也可以通過別的刻劃方法，使機率圖靈機所刻劃的普通函式類，以部分遞歸函式類作為其真子類。在相對可計算性方面也有類似的結果。
機率時序機
它是時序機（見有限自動機論）的推廣。其形式定義可以用五元組=(，，，，)給出，其中，，，仍如前所述，是條件機率
(;|;)
,機率時序機被構想為理想化了的離散物理系統。它有有限個不同的內部狀態，而且有下面兩種性質：①如果現時狀態是,輸入字母,則(;|;)表示輸出的字母是，並且下一時刻狀態為的聯合條件機率:②如果時序機開始時處於狀態 ，並且輸入字母依次是，，…，，則輸出字母序列，，…，的機率是[294-06]仙農首先用這一數學模型描述離散噪聲通信信道。因而關於機率時序機所得到的結果，既可以解釋為非機率時序機理論所得結果的對應推廣，又可以解釋為有限狀態通信信道的結構性質。
如果，，並且對於每一個正整數[295-01]對所有的[295-02]都成立，就稱狀態和是等價的。等價狀態產生相同的“輸入－輸出關係”。研究狀態等價的充分必要條件，是機率時序機理論的研究內容之一。
如同在非機率時序機情況，多餘的等價狀態可以被消除，從而得到一個化簡了的時序機。對於機率時序機，它的化簡了的形式不是唯一的，這一點和確定的時序機的情況有所不同。對於一個給定的機率時序機，可以找到一個尋求它的所有化簡形式的計算方法。
機率有限識別器
只有輸入沒有輸出的有限識別器的推廣。它的形式定義可以用=(，，，，)給出。其中[kg2]和仍表示輸入字母表和狀態集合，是初始分布，[295-03]是規定的終止狀態集合。(│，)是當輸入一個字母[kg1]時,狀態從轉移到的機率,簡記為()()為以[kg1]()為元素的矩陣[295-0]是一個列矢量,它的維數等於內元素的個數,它相應於中的元素的分量等於1,其餘的分量都是0,[295-07](…)=()()[9999]()[295-0]表示以為初始分布,輸入字…後，狀態進入終止集合 的機率。假定預先給定一個門限值(0≤的字…構成一個集合,稱為機率有限識別器按切斷點所識別的（或接受的）的隨機語言,用集合的記號記為
[295-04]是中的字母所能構成的一切字的集合。
隨機語言類包含有限識別器所識別的正則語言類作為其真子類，因而機率有限識別器是有限識別器的真推廣。隨機語言類對運算的封閉性，它的結構以及它與正則語言類的關係都是研究的重要內容。另一個問題是所謂穩定性問題。即對一個給定的機率識別器，轉移機率的微小擾動所引起的(,)中變化情況的研究。
多階段判決過程
機率自動機也可以用於多階段判決過程。在這一過程中，從一個狀態到另一狀態的轉移都附有一個條件機率和補償因子假設對個狀態的機率自動機從狀態轉移到狀態的補償因子是,則對於機率自動機在處一步轉移中的補償的數學期望值是
[295-05]由此可以求出在步之後的全部補償。
機率自動機的定義機率自動機的熵為
[295-06]其中 ()是自動機在步轉移之後處於狀態的機率。熵的概念可以用於模式識別和可靠性問題的研究。用機率自動機描述不可靠自動機時，熵可以作為有限自動機的可靠性的測度。可靠性隨著熵的減小而增加，可靠自動機的熵是零。
機率自動機理論與資訊理論、可靠性理論、自學習理論和模式識別、控制論、程式設計和馬爾可夫鏈的函式理論都有著密切的聯繫。圖靈機，各型形式語言的機率性推廣，具有機率性結構的樹自動機，機率自動機與動態規劃的關係，以及從範疇論觀點對隨機自動機的研究，都是一些有意義的研究課題。
