论文标题
通过过程代数更好的自动机
Better Automata through Process Algebra
论文作者
论文摘要
本文展示了在流程代理社区推广的样式中使用结构操作语义（SOS）如何导致从正则表达式构建有限自动机的更简洁和有用的结构。这种结构已知数十年，并构成了克莱恩定理一个方向的证据的基础。一方面，新结构的目的是向学生展示如何构建小型自动机，而无需空过渡，另一方面，以表明构造方法如何接受与其他操作员相对于其他操作员的封闭证明。这些结果虽然在理论上并不令人惊讶，但它表明了过程 - 地面研究的额外影响：除了提供对并发计算本质的基本见解外，它还为自动机理论中的旧，众所周知的结构提供了新的启示。
This paper shows how the use of Structural Operational Semantics (SOS) in the style popularized by the process-algebra community can lead to a more succinct and useful construction for building finite automata from regular expressions. Such constructions have been known for decades, and form the basis for the proofs of one direction of Kleene's Theorem. The purpose of the new construction is, on the one hand, to show students how small automata can be constructed, without the need for empty transitions, and on the other hand to show how the construction method admits closure proofs of regular languages with respect to other operators as well. These results, while not theoretically surprising, point to an additional influence of process-algebraic research: in addition to providing fundamental insights into the nature of concurrent computation, it also sheds new light on old, well-known constructions in automata theory.
