[科普中国]-概率自动机

在数学和计算机科学中，概率自动机(Probabilistic Automaton，PA)是非确定性有限自动机的推广; 它包括给定转换到转换函数的概率，将其转换为转换矩阵。 因此，概率自动机概括了马尔可夫链或有限类型的子移位的概念。 概率自动机识别的语言称为随机语言; 这些包括常规语言作为子集。 随机语言的数量是不可数的。

介绍概率自动机(probabilistic automaton)亦称随机自动机一种自动机。是所处环境或内部具有有限或无限的随机因素的自动机，与非概率型自动机的主要区别是：概率自动机的动作是随机的。每个概率自动机一般都需规定两组概率：一是给定自动机的初始状态的概率分布—初始分布，一般用一个随机矢量表示；二是规定在自动机处于某一状态，并向自动机输人某个字母的条件下，自动机下一动作(如状态转移、输出某个字母、改写字母等)的条件概率函数。有了这两组概率，就可计算自动机到达某个最终状态的概率。包含有不可靠元件的数字电路和通信的信道都可以表示为概率自动机。

定义概率自动机可以被定义为非确定性有限自动机（ ，Σ， ， ， ）的扩展，以及两个概率：发生特定状态转换的概率 ，以及初始状态 由随机向量代替，给出自动机处于给定初始状态的概率。

对于普通的非确定性有限自动机，人们有：

一组有限的状态 。

一组有限的输入符号Σ。

过渡函数 ： ×Σ→ （ ）。

一组状态 区分为接受（或最终）状态 ⊂ 。

这里， （ ）表示 的幂集。

通过使用currying，非确定性有限自动机的转移函数 ： ×Σ→ （Q）可以写成隶属函数。

： ×Σ× →{0,1}

因此，如果 '∈ （ ， ），则（ ， ， '）= 1，如果'= （ ， ），则 （ ，a， '）= 0。 咖喱变换函数可以理解为具有矩阵条目的矩阵。

'= （ ， ， '）

矩阵 然后是方阵，其条目为零或一，表示NFA是否允许转换 → '。总是为非确定性有限自动机定义这种转移矩阵。

对于字母表Σ中的每个符号 ，概率自动机用一系列随机矩阵 替换这些矩阵，以便通过下式给出转换的概率：

当然，从某个州到任何州的状态变化必须以概率1发生，因此必须具有

对于所有输入字母 和内部状态。概率自动机的初始状态由行向量v给出，其组件加到1：

转移矩阵作用于右侧，因此在消耗输入字符串a b c之后概率自动机的状态将是

特别地，概率自动机的状态总是随机向量，因为任意两个随机矩阵的乘积是随机矩阵，并且随机向量和随机矩阵的乘积也是随机向量。这个向量有时被称为状态分布，强调它是一个离散的概率分布。

形式上，概率自动机的定义不需要非确定性自动机的机制，这可以省略。形式上，概率自动机被定义为元组（，Σ，，，）。拉宾自动机是初始分布是坐标向量的自动机;也就是说，除了一个条目之外的所有条目都为零，其余条目为1。

属性每种常规语言都是随机的，更强烈的是，每种常规语言都是η-随机的。 一个弱的反面是每个0随机语言都是正则的; 然而，一般的反过来并不成立：有一些不规则的随机语言。

每个η-随机语言都是随机的，对于某些0