{"id":170,"date":"2021-06-07T11:14:22","date_gmt":"2021-06-07T03:14:22","guid":{"rendered":"https:\/\/swordofmorning.com\/?p=170"},"modified":"2025-10-09T13:56:21","modified_gmt":"2025-10-09T05:56:21","slug":"compilation-principle-01-regular-expression-constructs-nfa-nfa-constructs-dfa","status":"publish","type":"post","link":"https:\/\/swordofmorning.com\/index.php\/2021\/06\/07\/compilation-principle-01-regular-expression-constructs-nfa-nfa-constructs-dfa\/","title":{"rendered":"\u7f16\u8bd1\u539f\u7406 01 \u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u9020NFA &#038;&#038; NFA\u6784\u9020DFA"},"content":{"rendered":"<p><div class=\"has-toc have-toc\"><\/div><br \/>\n&emsp;&emsp;\u8003\u8651\u8fd9\u6837\u4e00\u4e2a\u95ee\u9898\uff1a\u4e3ar = (a|b)*abb\u6784\u9020\u4e00\u4e2aDFA\u3002<br \/>\n&emsp;&emsp;\u5bf9\u4e8e\u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u9020DFA\u7684\u95ee\u9898\uff1a\u7b2c\u4e00\u6b65\uff0c\u4e3a\u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u9020\u4e00\u4e2aNFA\uff1b\u7b2c\u4e8c\u6b65\uff0c\u7531NFA\u8f6c\u6362\u4e3aDFA\u8868\u8fbe\u5f0f\u3002<\/p>\n<h2>\u4e00\u3001\u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u9020NFA<\/h2>\n<p><em>\u53c2\u8003\uff1a\u300a\u7f16\u8bd1\u539f\u7406\u300b\u9f99\u4e66\uff0cp102\u3002<\/em><\/p>\n<h3>step 1: \u7531\u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u5efa\u8bed\u6cd5\u6811<\/h3>\n<p>&emsp;&emsp;r = (a|b)*abb<\/p>\n<figure style=\"width: 281px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/Regex_Tree.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"281\" height=\"301\" alt=\"\u56fe1\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/Regex_Tree.png\" width=\"281\" height=\"301\" alt=\"\u56fe1\" class=\"size-full\" \/><\/noscript> \u56fe1\uff1a\u8bed\u6cd5\u6811<\/figcaption><\/figure>\n<h3>step 2: \u4e3a\u5404\u5b50\u5f0f\u6784\u9020NFA<\/h3>\n<h4>1.2.1 \u5bf9\u4e8er1\u548cr2\u6784\u9020NFA<\/h4>\n<figure style=\"width: 331px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r1r2_NFA.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"331\" height=\"141\" alt=\"\u56fe2\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r1r2_NFA.png\" width=\"331\" height=\"141\" alt=\"\u56fe2\" class=\"size-full\" \/><\/noscript> \u56fe2\uff1a\u4e3ar1\u3001r2\u6784\u9020NFA<\/figcaption><\/figure>\n<h4>1.2.2 \u5bf9r1\u548cr2\u4f7f\u7528\u5e76\u8fd0\u7b97\u5f97\u5230r3<\/h4>\n<figure style=\"width: 501px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r3_NFA.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"501\" height=\"121\" alt=\"\u56fe3\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r3_NFA.png\" width=\"501\" height=\"121\" alt=\"\u56fe3\" class=\"size-full\" \/><\/noscript> \u56fe3\uff1ar3\u7684NFA<\/figcaption><\/figure>\n<h4>1.2.3 \u5bf9r6\u3001r8\u3001r10\u6784\u9020NFA<\/h4>\n<figure style=\"width: 331px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r6r8r10_NFA.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"331\" height=\"221\" alt=\"\u56fe4\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r6r8r10_NFA.png\" width=\"331\" height=\"221\" alt=\"\u56fe4\" class=\"size-full\" \/><\/noscript> \u56fe4\uff1ar6\u3001r8\u3001r10\u7684NFA<\/figcaption><\/figure>\n<h4>1.2.4 \u5bf9r6\u3001r8\u3001r10\u4f7f\u7528\u8fde\u63a5\u8fd0\u7b97<\/h4>\n<figure style=\"width: 560px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r6r8r10and_NFA.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"560\" height=\"61\" alt=\"\u56fe5\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/r6r8r10and_NFA.png\" width=\"560\" height=\"61\" alt=\"\u56fe5\" class=\"size-full\" \/><\/noscript> \u56fe5\uff1a\u8fde\u63a5\u8fd0\u7b97<\/figcaption><\/figure>\n<h4>1.2.5 \u8fde\u63a52\u548c4\u4e2d\u7684\u4e24\u90e8\u5206<\/h4>\n<figure style=\"width: 1098px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\"   class=\"lazyload\" data-src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/total_NFA.png\" src=\"https:\/\/cdn.jsdelivr.net\/gh\/moezx\/cdn@3.0.2\/img\/svg\/loader\/trans.ajax-spinner-preloader.svg\" onerror=\"imgError(this)\"  width=\"1098\" height=\"226\" alt=\"\u56fe6\" class=\"size-full\" \/ ><figcaption class=\"wp-caption-text\"><noscript><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/cdn.swordofmorning.com\/SwordofMorning\/Article%20Images\/Compile%20Principle\/01\/total_NFA.png\" width=\"1098\" height=\"226\" alt=\"\u56fe6\" class=\"size-full\" \/><\/noscript> \u56fe6\uff1a\u6700\u7ec8\u5f97\u5230\u7684NFA<\/figcaption><\/figure>\n<h2>\u4e8c\u3001NFA\u6784\u9020DFA<\/h2>\n<p>&emsp;&emsp;r = (a|b)*abb<br \/>\n&emsp;&emsp;\u5728\u7b2c\u4e00\u8282\u4e2d\uff0c\u6211\u4eec\u5df2\u7ecf\u5f97\u5230\u4e86r\u5bf9\u5e94\u7684NFA\uff0c\u4e0b\u9762\u6211\u4eec\u901a\u8fc7NFA\u6765\u6784\u9020DFA\u3002<\/p>\n<h3>step 1: \u6c42\u5f97start\u7b49\u4ef7\u5f00\u59cb\u72b6\u6001\u96c6\u5408<\/h3>\n<p>&nbsp;&nbsp;&nbsp;&nbsp;\u4ece\u72b6\u60010\u53ef\u4ee5\u901a\u8fc7Epsilon\u5230\u8fbe\u7684\u72b6\u6001\u6709{0, 1, 2, 4, 7}\uff0c\u8fd9\u91cc\u5305\u542b\u4e86\u672c\u8eab0\u72b6\u6001\uff0c\u8bb0\u4f5cA = {0, 1, 2, 4, 7}\uff0cA\u4e3aNFA\u7684\u8d77\u59cb\u72b6\u6001\u96c6\u5408\u3002<\/p>\n<h3>step 2: \u5bfb\u627e\u6807\u8bb0\u7b26\u53f7<\/h3>\n<p>&nbsp;&nbsp;&nbsp;&nbsp;\u8fd9\u91cc\u7684\u8f93\u5165\u6709{a, b}\u4e24\u79cd\uff0c\u6240\u4ee5\u4f7f\u7528a\u548cb\u6765\u6807\u8bb0NFA\u72b6\u6001\u96c6\u5408\u3002<\/p>\n<h3>step 3: \u6807\u8bb0\u72b6\u6001\u96c6\u5408<\/h3>\n<h4>2.3.1 \u4f7f\u7528{a, b}\u6807\u8bb0A<\/h4>\n<p>\\begin{align}<br \/>\nDtran[A, a] &amp;= Epsilon-Closure(move(A, a))\\newline<br \/>\n&amp;= Epsilon-Closure({3, 8})\\newline<br \/>\n&amp;= {1, 2, 3, 4, 6, 7, 8} = B\\newline<br \/>\n&amp;B\u8fd9\u91cc\u5305\u542b\u4e86\u672c\u8eab{3, 8}\u72b6\u6001\uff0c\u4e0b\u540c\u3002<br \/>\n\\end{align}<\/p>\n<p>\\begin{align}<br \/>\nDtran[A, b] &amp;= Epsilon-Closure(move(A, b))\\newline<br \/>\n&amp;= Epsilon-Closure({5})\\newline<br \/>\n&amp;= {1, 4, 5, 6, 7} = C<br \/>\n\\end{align}<br \/>\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Dtran[A, a]\u8868\u793a\u4eceDFA\u72b6\u6001A\u53ef\u4ee5\u5230\u8fbe\u7684DFA\u72b6\u6001\u3002move(A, a)\u8868\u793a\u4ece\u72b6\u6001A\u53ef\u4ee5\u5230\u8fbe\u7684\u70b9\uff08NFA\u72b6\u6001\uff09\uff0c\u672c\u4f8b\u4e2d\u662f{3, 8}\u3002Epsilon-Closure({3, 8})\u5728\u672c\u4f8b\u4e2d\u8868\u793a\u4ece{3, 8}\u85c9\u7531a\u548cEpsilon\u53ef\u4ee5\u5230\u8fbe\u7684\u70b9\u7684\u96c6\u5408\u3002<\/p>\n<h4>2.3.2 \u4f7f\u7528{a, b}\u6807\u8bb0B\u3001C<\/h4>\n<p>\\begin{align}<br \/>\nDtran[B, a] &amp;= Epsilon-Closure(move(B, a))\\newline<br \/>\n&amp;= Epsilon-Closure({3, 8})\\newline<br \/>\n&amp;= {1, 2, 3, 4, 6, 7, 8} = B<br \/>\n\\end{align}<br \/>\n\\begin{align}<br \/>\nDtran[B, b] &amp;= Epsilon-Closure(move(B, b))\\newline<br \/>\n&amp;= Epsilon-Closure({5, 9})\\newline<br \/>\n&amp;= {1, 2, 4, 5, 6, 7, 9} = D<br \/>\n\\end{align}<br \/>\n\\begin{align}<br \/>\nDtran[C, a] &amp;= Epsilon-Closure(move(C, a))\\newline<br \/>\n&amp;= Epsilon-Closure({3, 8})\\newline<br \/>\n&amp;= {1, 2, 3, 4, 6, 7, 8} = B<br \/>\n\\end{align}<br \/>\n\\begin{align}<br \/>\nDtran[C, b] &amp;= Epsilon-Closure(move(C, b))\\newline<br \/>\n&amp;= Epsilon-Closure({5})\\newline<br \/>\n&amp;= {1, 4, 5, 6, 7} = C<br \/>\n\\end{align}<\/p>\n<h4>2.3.3 \u4f7f\u7528{a, b}\u6807\u8bb0D<\/h4>\n<p>\\begin{align}<br \/>\nDtran[D, a] &amp;= Epsilon-Closure(move(D, a))\\newline<br \/>\n&amp;= Epsilon-Closure({3, 8})\\newline<br \/>\n&amp;= {1, 2, 3, 4, 6, 7, 8} = B<br \/>\n\\end{align}<br \/>\n\\begin{align}<br \/>\nDtran[D, b] &amp;= Epsilon-Closure(move(D, b))\\newline<br \/>\n&amp;= Epsilon-Closure({5, 10})\\newline<br \/>\n&amp;= {1, 2, 4, 5, 6, 7, 10} = E<br \/>\n\\end{align}<\/p>\n<h4>2.3.4 \u4f7f\u7528{a, b}\u6807\u8bb0E<\/h4>\n<p>\\begin{align}<br \/>\nDtran[E, a] &amp;= Epsilon-Closure(move(E, a))\\newline<br \/>\n&amp;= Epsilon-Closure({3, 8})\\newline<br \/>\n&amp;= {1, 2, 3, 4, 6, 7, 8} = B<br \/>\n\\end{align}<br \/>\n\\begin{align}<br \/>\nDtran[E, b] &amp;= Epsilon-Closure(move(E, b))\\newline<br \/>\n&amp;= Epsilon-Closure({5})\\newline<br \/>\n&amp;= {1, 4, 5, 6, 7} = C<br \/>\n\\end{align}<\/p>\n<h3>step 4: \u72b6\u6001\u5168\u90e8\u88ab\u6807\u8bb0\uff0c\u53ef\u5217\u8868<\/h3>\n<table>\n<thead>\n<tr>\n<th>NFA\u72b6\u6001\u96c6\u5408<\/th>\n<th>DFA\u72b6\u6001<\/th>\n<th>\u901a\u8fc7a\u5230\u8fbe\u7684DFA<\/th>\n<th>\u901a\u8fc7b\u5230\u8fbe\u7684DFA<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>{0, 1, 2, 4, 7}<\/td>\n<td>A<\/td>\n<td>B<\/td>\n<td>C<\/td>\n<\/tr>\n<tr>\n<td>{1, 2, 3, 4, 6, 7, 8}<\/td>\n<td>B<\/td>\n<td>B<\/td>\n<td>D<\/td>\n<\/tr>\n<tr>\n<td>{1, 4, 5, 6, 7}<\/td>\n<td>C<\/td>\n<td>B<\/td>\n<td>C<\/td>\n<\/tr>\n<tr>\n<td>{1, 2, 4, 5, 6, 7, 9}<\/td>\n<td>D<\/td>\n<td>B<\/td>\n<td>E<\/td>\n<\/tr>\n<tr>\n<td>{1, 2, 4, 5, 6, 7, 10}<\/td>\n<td>E<\/td>\n<td>B<\/td>\n<td>C<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>step 5: \u6839\u636e\u8868\u753b\u56fe<\/h3>\n<p>&nbsp;&nbsp;&nbsp;&nbsp;\u6211\u61d2\u5f97\u753b\u4e86\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&emsp;&emsp;\u8003\u8651\u8fd9\u6837\u4e00\u4e2a\u95ee\u9898\uff1a\u4e3ar = (a|b)*abb\u6784\u9020\u4e00\u4e2aDFA\u3002 &emsp;&emsp;\u5bf9\u4e8e\u6b63\u5219\u8868\u8fbe\u5f0f\u6784\u9020 &#8230;<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/170"}],"collection":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":11,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/170\/revisions"}],"predecessor-version":[{"id":444,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/posts\/170\/revisions\/444"}],"wp:attachment":[{"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/media?parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/categories?post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/swordofmorning.com\/index.php\/wp-json\/wp\/v2\/tags?post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}