regex - 任何有限状态自动机都可以转换为正则表达式吗？

Question

假设我们的 fsa 如下:

fsa = {0:{'a': 1, else: 2},1:{'b': 1, else: 2},2:{else: 2}}

这意味着:在状态0，如果输入是“a”，则进入状态1，否则进入状态2；在状态1，如果输入是“b”，则进入状态1，否则进入状态2；在状态 2，对于任何输入，它都会进入状态 2。

假设状态0是开始状态，状态1是接受状态，状态2是失败状态。那么这个 fsa 可以被翻译为正则表达式“ab*”。事实上，有一些算法可以将 fsa 转换为正则表达式，例如 Brzozowski 代数方法。

我的问题:上面表格中定义的任何 fsa 都可以转换为正则表达式吗？有什么限制吗？

Answer 1

是的，它们在数学上是等价的。 'The equivalence of regular expressions and finite automata is known as Kleene's theorem. '