1 基本概念
概率自动机是自动机理论中的一种扩展模型，它在状态转移、接受判断或输出生成中引入随机因素，用概率而非唯一确定的规则描述系统行为。它适用于刻画那些既有离散结构、又含不确定性的计算过程，例如随机算法、噪声环境中的识别任务以及某些动态系统的抽象表示。
1.1 定义
一般而言，概率自动机可以看作在给定输入下，以一定概率从当前状态转移到若干后继状态的机器。与传统自动机不同，它并不要求每一步的演化唯一确定，而是允许同一输入对应多个可能结果，并由概率分布决定各结果出现的可能性。
在不同文献中，概率自动机的定义略有差异。有的侧重“状态转移概率”，有的强调“接受概率”，还有的把输出过程也纳入概率化描述。尽管形式不同，它们的共同点都是：系统运行具有随机性，且该随机性是预先规定并可计算的。
1.2 形式化表示
概率自动机通常由状态集合、输入字母表、转移概率函数以及初始状态和接受条件等部分组成。其形式化表示为后续分析语言识别能力、运行结果和理论性质提供了基础。
1.2.1 状态集
状态集表示自动机可能处于的全部内部配置。若模型是有限的，则状态集通常为有限集合；若考虑更复杂的扩展，则也可包含无限多个状态。每个状态对应系统在某一时刻的内部记忆或控制位置。
1.2.2 输入字母表
输入字母表是自动机可读取符号的集合。输入串由字母表中的符号按顺序组成，自动机依次读取这些符号，并根据当前状态与当前输入符号决定下一步的概率性演化。
1.2.3 转移概率函数
转移概率函数是概率自动机的核心，描述在某一状态读取某个输入符号后，转移到各个后继状态的概率分布。对于固定的当前状态和输入符号，所有可能后继状态的转移概率之和通常为1。
1.2.4 初始状态与接受条件
初始状态给出了计算开始时自动机所在的位置。接受条件则规定何种运行结果应被视为“接受”。在概率自动机中，接受条件可以是终止于某些状态，也可以是累计接受概率超过某个阈值，或者在规定的运行时长后根据最终分布判断。
1.3 概率自动机与确定性自动机的区别
确定性自动机在每个状态和输入符号下只有唯一的下一步，因此其行为完全可预测。概率自动机则允许多个后继状态，并以概率方式选择，因而具有随机性和统计意义上的结果。
这种差异带来两方面影响：一方面，概率自动机更适合建模现实中的不确定过程；另一方面，其理论分析往往更复杂，尤其是在语言识别阈值、等价性和极限行为等问题上，处理难度明显高于确定性情形。
1.4 核心性质
概率自动机的核心性质主要体现在三点：其一，状态演化遵循概率规律；其二，运行结果通常依赖整体路径而非单一步骤；其三，许多性质只能从统计意义或极限意义上理解。
此外，概率自动机常与马尔可夫结构密切相关，因此可借助概率论和线性代数工具进行分析。其研究也常涉及可识别性、闭包性、稳定性以及算法可判定性等问题。
2 类型划分
概率自动机可以按照输出机制、状态规模和计算场景进行分类。不同分类方式强调的侧重点不同，但都服务于对随机计算模型的细化理解。
2.1 按输出机制分类
2.1.1 仅转移概率模型
这类模型只在状态转移中引入概率，不显式给出输出。系统的关注重点是状态随输入变化的随机演化过程，常用于形式语言识别和系统行为分析。
2.1.2 带接受概率模型
这类模型在运行结束后给出接受或拒绝的概率。与单纯的终态判断相比，它更灵活，也更适合研究阈值接受和近似识别等问题。
2.1.3 带输出概率模型
此类模型不仅在转移过程中具有概率性，还可能在每一步或最终阶段输出符号、标签或数值，并按概率分布决定输出内容，常用于生成任务和序列建模。
2.2 按状态数量分类
2.2.1 有限概率自动机
有限概率自动机具有有限个状态，是研究中最常见的基本形式。由于结构简洁，它便于数学分析，也更容易与有限自动机、马尔可夫链等模型建立对应关系。
2.2.2 无限概率自动机
无限概率自动机允许状态空间无限，因而能描述更复杂的系统。不过，这类模型的分析通常更困难，许多传统结论不再直接适用。
2.3 按计算场景分类
2.3.1 识别型概率自动机
识别型模型主要用于判断输入串是否属于某个语言集合。它们通常通过接受概率来表达识别结果，因而在形式语言理论中占有重要位置。
2.3.2 生成型概率自动机
生成型模型侧重于输出序列的产生，可视为从概率规则中抽样得到符号串的过程。它们常见于文本生成、序列模拟和随机过程建模。
2.3.3 决策型概率自动机
决策型模型将概率机制用于选择行动或判断结果，常用于抽象决策过程、协议执行和带噪控制系统。其重点在于在不确定条件下形成可分析的决策规则。
3 数学基础
概率自动机的理论基础主要来自概率论、线性代数和随机过程。借助这些工具，可以对其转移、收敛与长期行为进行系统分析。
3.1 概率论基础
3.1.1 概率分布
概率分布描述随机变量或状态集合中各事件发生的可能性。对于概率自动机而言，转移概率函数本质上就是一种分布，用于规定每一步的随机选择方式。
3.1.2 条件概率
条件概率用于描述在已知当前状态和输入符号的前提下，下一状态出现的概率。它是概率自动机一步转移的基本计算单位。
3.1.3 随机过程
概率自动机的运行可视为一个离散时间随机过程。其状态序列随输入和随机选择而变化，适合用随机过程的框架分析路径分布与长期性质。
3.2 线性代数表示
3.2.1 转移矩阵
转移矩阵将状态之间的概率关系用矩阵形式表示。矩阵中的元素对应状态间的转移概率，便于统一计算多个步骤的演化结果。
3.2.2 向量状态表示
在向量表示中，系统当前状态用概率向量描述，其中每个分量表示处于某个状态的概率。该表示方式直观而简洁，适合与矩阵运算结合。
3.2.3 矩阵迭代计算
通过不断乘以转移矩阵，可以得到多步运行后的状态分布。这种迭代计算是分析概率自动机长期行为的常用方法。
3.3 马尔可夫过程联系
3.3.1 马尔可夫链
概率自动机在不依赖过去全部历史、而只依赖当前状态的情况下，常可表示为马尔可夫链。二者在数学结构上高度相似，因此可以共享许多分析工具。
3.3.2 吸收态与稳态
吸收态是指一旦进入就不再离开的状态，常用于建模终止或完成过程。稳态则指长期运行后趋于稳定的概率分布，反映系统的极限行为。
3.3.3 随机游走模型
随机游走是概率自动机的重要参照模型之一。它描述系统在状态空间中按随机规则逐步移动的过程，常用于理解路径选择、扩散现象和到达概率。
4 运行机制
概率自动机的运行可理解为输入驱动下的概率演化过程。其结果不依赖单一路径，而是由所有可能路径及其概率共同决定。
4.1 输入驱动的状态转移
自动机在读取输入串时，按照当前状态和当前符号触发概率转移。每读取一个符号，系统就根据对应的转移规则更新状态分布，直到输入处理完毕。
4.2 概率累积与路径计算
一条具体运行路径的概率等于该路径上各步转移概率的连乘。若多个不同路径导向同一结果，则需要将这些路径概率累加，得到最终的整体概率。
4.3 接受概率的判定
接受概率通常由所有接受路径或接受状态上的概率总和计算得出。根据模型设定，最终结果可以通过固定阈值、比较规则或终止状态判定。
4.4 运行结果的统计解释
由于单次运行具有随机性，概率自动机的输出更适合从统计角度理解。某一语言是否被接受，不一定取决于一次试验，而常依赖长期频率和概率阈值。
4.5 多次运行与经验分布
对同一输入多次运行概率自动机，观察得到的结果频率，可形成经验分布。经验分布与理论分布之间的差异，反映了采样次数和模型稳定性的影响。
5 计算能力与理论性质
概率自动机在计算能力上介于确定性模型与更强的随机化模型之间，其理论研究涉及可识别语言类、判定问题、闭包性质和极限行为等。
5.1 可识别语言类
5.1.1 正则语言中的概率识别
许多概率自动机能够识别正则语言的变体，并以概率方式实现接受。对于经典正则语言，它们通常可以给出与确定性自动机相兼容的识别方式。
5.1.2 非确定性与随机化差异
非确定性自动机强调“存在一条可接受路径”，而概率自动机强调“可接受路径的概率总量”。两者虽都允许多分支，但判断标准本质不同。
5.2 可判定问题
5.2.1 空语言判定
空语言判定关注某个概率自动机是否对任何输入都无法达到接受条件。该问题在不同模型中复杂度不一，有时可判定，有时则难以处理。
5.2.2 等价性问题
等价性问题是判断两个概率自动机是否对所有输入给出相同识别结果。由于涉及无限多个输入串和概率分布比较，通常比确定性情形更困难。
5.2.3 包含性问题
包含性问题研究一个自动机识别的语言是否完全包含于另一个自动机识别的语言之中。对于概率模型，这一问题可能需要同时考虑语言集合与接受阈值。
5.3 闭包性质
5.3.1 并运算
若两个语言分别可由概率自动机识别，则它们在一定条件下的并集也可能可由同类模型表示。具体结论取决于接受阈值和模型设定。
5.3.2 交运算
交运算对应同时满足两个识别条件。概率模型中常通过并行构造或概率组合实现，但闭包结果往往比确定性自动机更细致。
5.3.3 补运算
补运算在概率自动机中并不总是自然成立，尤其当接受条件依赖阈值时，补集的识别方式可能需要重新构造模型。
5.4 极限行为
5.4.1 收敛性
概率自动机的状态分布在多步迭代后可能收敛到某种极限分布。收敛性是判断系统长期稳定的重要依据。
5.4.2 阈值接受
阈值接受是概率自动机中常见的判定方式，即当接受概率达到某个阈值时视为接受。阈值的设置会显著影响语言类与判定性质。
5.4.3 长期稳定性
长期稳定性关注系统经过长时间运行后是否进入稳定模式。若存在稳定分布或周期结构，则可据此分析其长期输出特征。
6 典型模型
概率自动机并非单一模型，而是一系列相关结构的统称。不同典型模型在表达能力和应用场景上各有侧重。
6.1 概率有限自动机
概率有限自动机是最基础的形式之一，通常具有有限状态和概率转移规则。它既可用于语言识别，也可用于描述简单的随机控制过程。
6.2 概率图灵机中的自动机子结构
在概率图灵机中，自动机子结构负责描述有限控制部分的随机行为。它将自动机思想与更强的计算模型结合，适用于研究随机计算复杂性。
6.3 加权自动机
加权自动机可视为概率自动机的推广或近亲，其转移不一定表示概率，也可表示权重、代价或评分。若权重满足归一化条件，则与概率模型关系密切。
6.4 量子自动机与概率自动机的比较
量子自动机同样具有非确定性表现，但其底层机制基于量子态和幅度，而非经典概率分布。与概率自动机相比，它们共享某些形式特征，却遵循不同的数学规则。
6.5 随机有限状态机
随机有限状态机通常用于工程和应用语境，强调有限状态结构中的随机转换与输出。它在语音处理、通信建模和序列分析中较为常见。
7 应用领域
概率自动机因能够自然表示不确定性，已被用于多个需要随机建模的领域。其优势在于结构清晰、可计算性较强，且便于与统计方法结合。
7.1 模式识别
在模式识别中，概率自动机可用于分类、序列判别和噪声环境下的特征匹配。它能通过概率评分提高对不完整或带干扰数据的适应性。
7.2 自然语言处理
自然语言处理中，概率自动机常用于词法分析、句法建模和序列预测。它能够表达语言中的不确定转移与多重可能性，因此适合处理模糊输入。
7.3 生物序列分析
在生物序列分析中，概率自动机可用于DNA、RNA或蛋白质序列的模式搜索与片段识别。其随机结构有助于刻画序列中的变异与噪声。
7.4 通信协议建模
通信协议常包含重试、丢包和随机延迟等现象，适合用概率自动机抽象描述。通过该模型，可以分析协议在不稳定环境中的行为路径。
7.5 系统可靠性分析
概率自动机可用于估计系统在随机故障条件下的运行结果。它能帮助分析失败概率、恢复过程以及不同策略对可靠性的影响。
7.6 随机算法设计
在随机算法设计中，概率自动机为算法步骤的随机选择提供形式化表达。借助这一模型，可分析算法正确率、期望时间和输出分布。
8 研究历史与发展
概率自动机的研究伴随着自动机理论和随机过程理论的发展逐步深化。其形式化框架经历了从早期探索到多方向扩展的过程。
8.1 早期形式化研究
早期研究主要关注如何在有限自动机框架中引入概率，并分析其对语言识别能力的影响。这一阶段奠定了概率有限自动机的基本定义与问题框架。
8.2 经典理论结果
经典理论结果集中在识别能力、阈值语言、闭包性质和判定问题等方面。许多结果表明，加入概率后，模型的表达与分析都比确定性情形更加微妙。
8.3 现代扩展方向
现代研究进一步引入加权、时间、并发和学习机制，使概率自动机能够描述更复杂的现实系统。与此同时，算法验证与统计推断也成为重要方向。
8.4 与其他形式模型的融合
概率自动机常与马尔可夫链、博弈模型、加权系统和量子模型相结合，形成复合式表达框架。这种融合有助于统一处理随机性、策略选择与系统验证。
9 相关概念
概率自动机处于多个数学与计算理论概念的交汇处，理解其含义通常需要结合若干邻近术语。
9.1 自动机理论
自动机理论研究抽象机器的计算过程，包括状态、输入、转移和接受机制。概率自动机是这一理论中的随机化扩展。
9.2 形式语言
形式语言是由符号串构成的集合，常作为自动机识别的对象。概率自动机通过接受概率刻画某些语言的识别方式。
9.3 随机过程
随机过程描述随时间演化的随机变量序列。概率自动机的状态变化可视作离散随机过程的一种特殊形式。
9.4 随机算法
随机算法在计算过程中使用随机选择，以提升效率、简化设计或增强适应性。概率自动机为这类算法提供了形式化抽象。
9.5 加权系统
加权系统在转移、路径或输出上附加权重信息，权重可以表示概率、成本或得分。它与概率自动机在数学结构上关系密切。
10 经典问题与研究方向
概率自动机研究中存在一系列基础而重要的问题，这些问题推动了理论深化，也促进了其在应用中的发展。
10.1 最小化问题
最小化问题关注如何在保持等价行为的前提下，减少状态数或简化结构。对于概率自动机而言，由于概率分布的约束，最小化往往比确定性自动机更难。
10.2 学习问题
学习问题研究如何根据样本数据推断概率自动机的结构和参数。常见任务包括状态恢复、转移概率估计和模型选择。
10.3 近似识别问题
近似识别问题允许模型以一定误差处理输入，强调在噪声和不完全信息下的鲁棒性。这在实际应用中尤为重要，因为严格识别往往过于理想化。
10.4 参数估计问题
参数估计问题主要指从观测数据中推断转移概率、初始分布或接受阈值等参数。它通常依赖统计推断方法，并与机器学习紧密相关。
10.5 模型验证问题
模型验证问题研究给定的概率自动机是否满足某些性质，如安全性、可达性或长期稳定性。由于概率因素的存在，验证往往需要结合数值计算与逻辑分析。