From regular expressions to finite automata
From regular expressions to finite automata
复制标题
从正则表达式到有限自动机
DOI：
10.1080/00207169908804865
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Ziadi
中科院分区：
文献类型：
--
作者：
Jean;J. Ponty;D. Ziadi
有三种经典算法可以从正则表达式计算有限的自动机。 Brzozowski算法产生确定性的自动机，Glushkov算法非确定性，而一般逐步的方法通常会产生带有电子过渡的NFA。 Berry和Sethi已经改编了Brzozowski的算法来计算表达式的Glushkov自动机。我们描述了逐步结构的变体，该变体将标准和修剪自动机关联到普通语言。我们表明，由变体和Glushkov Automaton构建的自动机（由Berry-Sethi算法计算）是同构的。
There are three classical algorithms to compute a finite automaton from a regular expression. The Brzozowski algorithm yields a deterministic automaton, the Glushkov algorithm a nondeterministic one, and the general step by step method generally yields a NFA with e-transitions. Berry and Sethi have adapted Brzozowski's algorithm to compute the Glushkov automaton of an expression. We describe a variant of the step by step construction which associates standard and trim automata to regular languages. We show that the automaton constructed by the variant and the Glushkov automaton (computed by Berry-Sethi algorithm) are isomorphic.