随机文法(卷名：自动控制与系统工程)
stochastic grammar
对每条文法产生式（重写规则）赋予一定的概率值以描述随机模式的文法。由随机文法产生的语言称为随机语言，接受随机语言的自动机称为随机自动机。在通信、信息存储和检索以及物理模式的测量处理等问题中不可避免地存在噪声和干扰，因此用于描述模式类的语言带有随机性质。为了从数学上表征语言 L的不确定性和随机性， 可以在文法产生式中引入概率度量 pij，即
，且
。设从起始符s开始通过使用产生式序列r1,r2,…,rm导出链x,与产生式r1,…,rm 相联系的概率分别是p(r1)，p(r2),…,p(rm),当概率 p(ri)(i=1,…,m)的大小不依赖于在它前面导出过程所使用的产生式时，则用上述序列导出句子x的概率是
当导出同一x存在k种不同的产生式序列时,句子x的导出概率是各个序列导出概率之和。与统计方法中贝叶斯分类器相类似,当同一条链由两种以上的文法产生时,则用能得到x最大导出概率的那个文法作为该链的句法描述。按照短语结构文法中αi→βj的不同限制条件,相应的有 0型（无限制）、1型（上下文敏感）、2型（上下文无关）和3型（有限状态）四种类型随机文法。
随机文法中的一个重要理论问题就是确定一致性条件,即文法所产生的全部句子的导出概率的和应等于1的条件。对于产生式形式为
（A，B为非终止符,u，v为终止符）的线性文法和上下文无关随机文法的一致性条件的检验，可分别利用有限状态马尔可夫过程和盖尔顿－华生分支理论来确定。随机上下文敏感文法的一致性问题，至今尚未得到解决。当把随机的概念应用到高维随机文法时，就得到随机树文法和相应的随机树语言、随机图文法和相应的随机图语言等。这种高维随机文法和语言能够有效地描述带有噪声与畸变的比较复杂的模式。