任何有限状态自动机都可以翻译成正则表达式吗？

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可以翻译成regex "ab*"。事实上，有一些算法可以将 fsa 转换为正则表达式，例如 Brzozowski 代数方法。

我的问题：以上形式定义的任何fsa都可以翻译成正则表达式吗？有什么限制吗？

Answer 1

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

Answer 2

没有限制——所有有限状态自动机都等价于一些正则表达式，所有正则表达式都等价于一些有限状态自动机。

Answer 3

是的，它们是等价的。从wikipedia page on regular languages开始，这些都是常规语言的等价定义。

1. 正则表达式的语言
2. 它是非确定性有限自动机 (NFA) 接受的语言
3. 它是确定性有限自动机 (DFA) 接受的语言
4. 可以通过正则语法生成
5. 它是交替有限自动机接受的语言
6. 可以通过前缀语法生成
7. 它可以被只读图灵机接受
8. 可以用单子二阶逻辑定义（Büchi-Elgot-Trakhtenbrot定理）
9. 它被一些有限幺半群识别，这意味着它是有限幺半群的一个子集的原像，在其字母表上的自由幺半群的同态下

Answer 4

是的。每个有限自动机都会有一个对应的正则表达式。 Kleene 定理证明了这个结果。通过将有限自动机划分为多个更小的有限自动机的并集，利用数学归纳法原理证明了该定理。可以找到证明 here.