从正则表达式到有穷自动机

Dear 丶 2022-03-22 09:07 206阅读 0赞

**一般实现的是从正则表达式到DFA的转换**

而从正则表达式直接转换成DFA是比较困难的，所以一般先转换成NFA（NFA更直观一些）。

# 根据RE构造NFA #

##  ϵ \\epsilon ϵ对应的NFA ##

![在这里插入图片描述][20190127161812959.png]

## 字母表 ∑ \\sum ∑中符号 α \\alpha α对应的NFA ##

![在这里插入图片描述][20190127161757840.png]

##  r = r 1 r 2 r=r\_1r\_2 r=r1r2对应的NFA ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

##  r = r 1 ∣ r 2 r=r\_1|r\_2 r=r1∣r2对应的NFA ##

![在这里插入图片描述][20190127161730771.png]

##  r = ( r 1 ) ∗ r=(r\_1)^\* r=(r1)∗对应的NFA ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

例： r = ( a ∣ b ) ∗ a b b r=(a|b)^\*abb r=(a∣b)∗abb对应的NFA

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]

[20190127161812959.png]: /images/20220322/906da1065ce44ad3ab0ef39d63a74eec.png
[20190127161757840.png]: /images/20220322/46cd5ab712184a409a3091fb40408f17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20220322/2df1d77ac65844b4ba6f125affb8c926.png
[20190127161730771.png]: /images/20220322/9ca0050ce88d42ff83a0ad9a6b2cb2ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20220322/9d8f07bfbc5948e6841f43e63f5f9ee6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20220322/2de661ae70ee455bac42702035702802.png