regex - 构造有限自动机

Question

您是否同意在正则表达式中：

((a|b)*(e|c)*)* 

是 a、b 和 c 的任意组合吗？或者你会说 c 总是在 a 和 b 之后。

Answer 1

通过我总是更喜欢从语义上描述正则表达式 RE。但也有一条规则，其中之一——“分布式法则”，对编写清理和优化的 RE 很有帮助：

(P | Q)*  ==  (P*Q*)*  == (P* | Q*)*

注：|是联合运算，P | Q与P | Q. 这里 P, Q 是正则表达式。

所以你表达：

     ((a|b)*(e|c)*)*       # P = (a|b)*  and Q = (e|c)*
=>   ((a|b) | (e|c))*      # (P* | Q*)* = (P | Q)*

正如我所说的联合顺序并不重要，所以这里( )是多余的。和

     ((a|b) | (e|c))*     
=>   (a | b | c | e)*

现在 * 表示重复应用 * 的某个模式的任意次数。在上面的表达式中 * 应用于a | b | c | e，并且在每次迭代中您可以选择任何一个符号，这意味着任何符号都出现在正则表达式中的任何其他符号之后 – 这意味着 'a'、'b'、'c 的任意组合', 'e' 是可能的。

它的 FA 非常简单：由单个状态 Q ₀和一个标记为所有四个符号的自循环组成。如下：

     __
     || 甲、乙、丙、乙
     ▼|
––►((Q 0 ))

Q 0既是初始状态又是最终状态