Several algorithms exist to transform an automaton into a regular expression that denotes its recognized language. Some of these algorithms, such as those by Brzozowski and McCluskey, McNaughton and Yamada, and Arden, can produce expressions whose width grows exponentially with the number of states in the automaton. Caron, Champarnaud, and Mignot proposed an algorithm that transforms any acyclic automaton into an extended regular expression with linear width with respect to the number of states. Few years before, Caron and Ziadi introduced another algorithm that also produces regular expressions with linear width. However, this algorithm is restricted to so-called Glushkov automata, which are isomorphic to those obtained through the Glushkov construction. These automata are characterized by specific structural properties, including the strong stability of their maximal cycles. In this paper, we present a novel algorithm for strongly stabilizing an automaton, which serves as a foundational step toward the Glushkovization of any automaton. The key advantage of this approach is that strong stabilization addresses the non-acyclic parts of the automaton, allowing other algorithms to handle the acyclic parts with optimal efficiency.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Toward the Glushkovization of Automata: The Strong Stabilization

  • Samira Attou,
  • Ludovic Mignot,
  • Clément Miklarz,
  • Florent Nicart

摘要

Several algorithms exist to transform an automaton into a regular expression that denotes its recognized language. Some of these algorithms, such as those by Brzozowski and McCluskey, McNaughton and Yamada, and Arden, can produce expressions whose width grows exponentially with the number of states in the automaton. Caron, Champarnaud, and Mignot proposed an algorithm that transforms any acyclic automaton into an extended regular expression with linear width with respect to the number of states. Few years before, Caron and Ziadi introduced another algorithm that also produces regular expressions with linear width. However, this algorithm is restricted to so-called Glushkov automata, which are isomorphic to those obtained through the Glushkov construction. These automata are characterized by specific structural properties, including the strong stability of their maximal cycles. In this paper, we present a novel algorithm for strongly stabilizing an automaton, which serves as a foundational step toward the Glushkovization of any automaton. The key advantage of this approach is that strong stabilization addresses the non-acyclic parts of the automaton, allowing other algorithms to handle the acyclic parts with optimal efficiency.