标题： 论随机自动机的理论 显示英文标题

标题： On the Theory of Stochastic Automata

摘要： 离散随机系统的理论是由香农和冯·诺伊曼的工作开创的。 虽然香农考虑了无记忆通信信道及其通过引入状态进行的推广，而冯·诺伊曼则研究了如何从不可靠组件中合成可靠系统。 拉宾和斯科特关于确定性有限状态自动机的基础工作导致了两个推广。 首先，卡莱尔和斯塔克研究的转移函数到条件分布的推广。 这进而导致了时间离散马尔可夫链的推广，其中链由多于一个转移概率矩阵控制。 其次，通过引入随机自动机来推广正则集，如拉宾所描述的。 随机自动机已经被很好地研究。 本报告基于克劳斯的宝贵书籍，对随机自动机进行了简要介绍。 这包括随机自动机理论的基本主题：等价性、最小化、约简、覆盖、可观测性和确定性。 然后研究了梅利和莫尔自动机的随机版本，最后将随机语言接受器作为非确定性有限状态接受器的推广进行考虑。 显示英文摘要

摘要： The theory of discrete stochastic systems has been initiated by the work of Shannon and von Neumann. While Shannon has considered memory-less communication channels and their generalization by introducing states, von Neumann has studied the synthesis of reliable systems from unreliable components. The fundamental work of Rabin and Scott about deterministic finite-state automata has led to two generalizations. First, the generalization of transition functions to conditional distributions studied by Carlyle and Starke. This in turn has led to a generalization of time-discrete Markov chains in which the chains are governed by more than one transition probability matrix. Second, the generalization of regular sets by introducing stochastic automata as described by Rabin. Stochastic automata are well-investigated. This report provides a short introduction to stochastic automata based on the valuable book of Claus. This includes the basic topics of the theory of stochastic automata: equivalence, minimization, reduction, covering, observability, and determinism. Then stochastic versions of Mealy and Moore automata are studied and finally stochastic language acceptors are considered as a generalization of nondeterministic finite-state acceptors.