[拼音]：gailü zidongjilun

[外文]：probabilistic automata theory

自动机论的次级学科，主要研究所处环境或内部具有（有限或无限的）随机因素的自动机。与非概率型自动机不同之处，是概率自动机的动作是随机的。为了给定概率自动机，首先必需规定在自动机处于某一状态，并向自动机输入某个字母的条件下，自动机下一动作（如状态转移，输出某个字母，改写字母等）的条件概率函数。其次是给定自动机的初始状态的概率分布──初始分布，一般用一个随机矢量π＝(π1，π2，…，πn)表示，其中各个πi都是非负的，且相加之和等于1。n是自动机状态的个数。 πi表示在开始时自动机处于第i个状态的概率。包含有不可靠元件的数字电路和通信的信道都可以表示为概率自动机。

早在40年代末，C.E.仙农在信息论的研究中，就提出了噪声信道的数学模型(见图)，它实际上就是一种概率自动机。50年代初，J.诺伊曼研究用不可靠元件构造可靠机器，这个问题发展成为现代的容错计算问题。但是直到50年代末，在R.W.阿西贝的著作中才给出一个形式定义的雏形。1963年M.O.拉宾比较严格地阐述了概率自动机的一些基本概念，并提出一些问题（如稳定性问题）。后来，A.帕兹等人的著作综述了这一方面的研究成果。60年代末至70年代，有更多的人进行了这方面的研究工作。

与一般的自动机理论相平行的，有概率图灵机、概率时序机、概率识别器等方面的研究工作。这些工作一方面是推广自动机已有的结果；另一方面也提出不少新的问题，丰富了自动机论的内容。

概率图灵机是图灵机的推广。它的形式定义可以用六元组M=(X，Y，Q，W，p，π)给出。其中Q和W分别是非空有限的状态 和带字母 。X和Y 分别是输入字母 和输出字母 ，且X∪Y吇W，Q∩W=Φ。π是初始分布。p(z，q′|q，ω)是已知概率图灵机现在的状态q，且注视在带字母ω 的条件下它的“下一动作”的概率。“下一动作”是下面三者之一。

（1）:用z代替ω，且转移到状态q′；

（2）z=R：读写头向右移一单元，且转移到状态q′；

（3）z＝L：读写头向左移一单元，且转移到状态q′。

在概率图灵机的研究中，对可计算随机函数，给出了定义并对可计算函数及其运算也都作了研究，而且还证明了图灵机的许多研究结果在概率图灵机的情况下仍然成立。函数代入、原始递归、求极小等运算对可计算随机函数都是封闭的。限制在普通函数类的范围内，可以证明部分可计算随机函数中的普通函数，恰好是部分递归函数。从这个意义上看，把图灵机推广到概率图灵机的计算能力没有增大。也可以通过别的刻划方法，使概率图灵机所刻划的普通函数类，以部分递归函数类作为其真子类。在相对可计算性方面也有类似的结果。

它是时序机（见有限自动机论）的推广。其形式定义可以用五元组M＝(X，Y，Q，p，π)给出，其中X，Y，Q，π仍如前所述，p是条件概率

p(y;q′|q;x)

x∈X　 y∈Y　q，q′∈Q

概率时序机被设想为理想化了的离散物理系统。它有有限个不同的内部状态，而且有下面两种性质：

（1）如果现时状态是q，输入字母x，则p(y;q′|q;x)表示输出的字母是y，并且下一时刻状态为q′的联合条件概率:②如果时序机开始时处于状态 q1，并且输入字母依次是x1，x2，…，xn，则输出字母序列y1，y2，…，yn的概率是

仙农首先用这一数学模型描述离散噪声通信信道。因而关于概率时序机所得到的结果，既可以解释为非概率时序机理论所得结果的对应推广，又可以解释为有限状态通信信道的结构性质。

如果q1，q2∈Q，并且对于每一个正整数n

对所有的都成立，就称状态q1和q2是等价的。等价状态产生相同的“输入－输出关系”。研究状态等价的充分必要条件，是概率时序机理论的研究内容之一。

如同在非概率时序机情况，多余的等价状态可以被消除，从而得到一个化简了的时序机。对于概率时序机，它的化简了的形式不是唯一的，这一点和确定的时序机的情况有所不同。对于一个给定的概率时序机，可以找到一个寻求它的所有化简形式的计算方法。

只有输入没有输出的有限识别器的推广。它的形式定义可以用M＝(X，Q，p，π，F)给出。其中X和Q仍表示输入字母表和状态 ，π是初始分布，是规定的终止状态 。p(qj│qi，x)是当输入一个字母x时，状态从qi转移到qj的概率，简记为pij(x)。p(x)为以pij(x)为元素的矩阵。是一个列矢量，它的维数等于Q内元素的个数，它相应于F中的元素的分量等于1，其余的分量都是0，(x1x2…xκ)=π·p(x1)·p(x2)p(xκ)·表示以π为初始分布，输入字x1x2…xκ后，状态进入终止 F的概率。假定预先给定一个门限值λ(0≤λ＜1)，则所有使得(x1x2…xκ)＞λ的字x1x2…xκ构成一个 ，称为概率有限识别器按切断点λ所识别的（或接受的）的随机语言，用 的记号记为

X*是X中的字母所能构成的一切字的 。

随机语言类包含有限识别器所识别的正则语言类作为其真子类，因而概率有限识别器是有限识别器的真推广。随机语言类对运算的封闭性，它的结构以及它与正则语言类的关系都是研究的重要内容。另一个问题是所谓稳定性问题。即对一个给定的概率识别器，转移概率的微小扰动所引起的T(M，λ)中变化情况的研究。

概率自动机也可以用于多阶段判决过程。在这一过程中，从一个状态到另一状态的转移都附有一个条件概率和补偿因子。假设对n个状态的概率自动机从状态qi转移到状态qj的补偿因子是eij，则对于概率自动机在qi处一步转移中的补偿的数学期望值是

由此可以求出在κ步之后的全部补偿。

定义概率自动机的熵为

其中 pi(κ)是自动机在κ步转移之后处于状态qi的概率。熵的概念可以用于模式识别和可靠性问题的研究。用概率自动机描述不可靠自动机时，熵可以作为有限自动机的可靠性的测度。可靠性随着熵的减小而增加，可靠自动机的熵是零。

概率自动机理论与信息论、可靠性理论、自学 理论和模式识别、控制论、程序设计和马尔可夫链的函数理论都有着密切的联系。图灵机，各型形式语言的概率性推广，具有概率性结构的树自动机，概率自动机与动态规划的关系，以及从范畴论观点对随机自动机的研究，都是一些有意义的研究课题。

严正声明：本文由历史百科网注册或游客用户浩民自行上传发布关于» 概率自动机论的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：浩民；本文链接：https://www.freedefine.cn/wenzhan/60066.html