{"id":246,"date":"2013-05-06T22:13:16","date_gmt":"2013-05-06T14:13:16","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=246"},"modified":"2013-05-06T22:13:16","modified_gmt":"2013-05-06T14:13:16","slug":"re-nfa-%e6%ad%a3%e5%88%99%e8%a1%a8%e8%be%be%e5%bc%8f-%e4%b8%8d%e7%a1%ae%e5%ae%9a%e8%87%aa%e5%8a%a8%e6%9c%ba","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=246","title":{"rendered":"re -&#062; NFA \u6b63\u5219\u8868\u8fbe\u5f0f-&#062;\u4e0d\u786e\u5b9a\u81ea\u52a8\u673a"},"content":{"rendered":"<p>\u6587\u7ae0\u6765\u81ea<a href=\"http:\/\/www.360doc.com\/content\/09\/0219\/10\/98111_2586955.shtml\">http:\/\/www.360doc.com\/content\/09\/0219\/10\/98111_2586955.shtml<\/a><br \/>\n\u4ee5\u53cahttp:\/\/hi.baidu.com\/tcet030840zxp\/item\/c923fe885ddd0329100ef3ec<\/p>\n<table>\n<tbody>\n<tr>\n<td width=\"670px\">\u6700\u8fd1\u5f97\u505a\u4e00\u4e9b\u8ddf\u81ea\u52a8\u673a\u6709\u5173\u7684\u4e1c\u4e1c\uff0c\u5176\u4e2d\u4e00\u90e8\u5206\u53ef\u4ee5\u7b80\u8981\u5730\u770b\u4f5c\u662f\u7531\u4e00\u5957\u6b63\u5219\u6587\u6cd5\u751f\u6210\u72b6\u6001\u81ea\u52a8\u673a\u7684\u8fc7\u7a0b\u3002<\/p>\n<h3>\u4ec0\u4e48\u662f\u6b63\u5219\u8868\u8fbe\u5f0f\uff1f<\/h3>\n<p>\u9996\u5148\u6211\u4eec\u770b\u770b\u4ec0\u4e48\u662f<a href=\"http:\/\/en.wikipedia.org\/wiki\/Regular_expression\" target=\"_blank\" rel=\"noopener noreferrer\">\u6b63\u5219\u8868\u8fbe\u5f0f<\/a>\u3002\u8fd9\u4e2a\u4e1c\u4e1c\u5462\uff0c\u4e00\u822c\u7528\u4e8e\u63cf\u8ff0\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\u96c6\u5408\u2014\u2014\u76f4\u63a5\u8bf4\u5c31\u662f\u4e00\u4e2a\u6b63\u5219\u8868\u8fbe\u5f0f\u53ef\u80fd\u53ef\u4ee5\u5339\u914d\u4e00\u5927\u5806\u5b57\u7b26\u4e32\uff0c\u800c\u8fd9\u4e00\u5927\u5806\u5b57\u7b26\u4e32\u53ef\u4ee5\u5f62\u6210\u4e00\u4e2a\u96c6\u5408\uff0c\u5b83\u4eec\u7684\u5171\u540c\u7279\u5f81\u5c31\u662f\u53ef\u4ee5\u88ab\u8fd9\u4e2a\u6b63\u5219\u8868\u8fbe\u5f0f\u5339\u914d\u3002\u5c31\u50cf\u53bb\u6b7b\u53bb\u6b7b\u56e2\uff0c\u4f46\u662f\u4e0d\u540c\u7684\u662f\u53bb\u6b7b\u53bb\u6b7b\u56e2\u7684\u56e2\u5458\u7684\u5171\u540c\u7279\u5f81\u662f\u4e0d\u88ab\u4efb\u4f55\u5f02\u6027\u6240\u5339\u914d\u2014\u2014\u4f46\u662f\u8fd9\u6ca1\u5173\u7cfb\uff0c\u6211\u4eec\u4e0d\u59a8\u53d6\u53bb\u6b7b\u53bb\u6b7b\u56e2\u7684\u8865\u96c6\u5c31\u884c\u4e86\u3002<br \/>\n\u53cd\u6b63\u6b63\u5219\u8868\u8fbe\u662f\u5f88\u597d\u5566\uff0c\u56e0\u4e3a\u4f60\u53ea\u8981\u7528\u4e00\u70b9\u70b9\u5728\u810f\u8bdd\u91cc\uff0c\u5c31\u53ef\u4ee5\u9a82\u597d\u591a\u597d\u591a\u4eba\uff0c\u6bd4\u5982\uff1a<\/p>\n<pre>Mar(y|k|cus) is son of bitch.<\/pre>\n<p>\u771f\u662f\u975e\u5e38de\u7701\u529b\uff0c\u552f\u4e00\u7684\u7f3a\u70b9\u662f\u53ef\u80fd\u5bf9\u65b9\u4e0d\u77e5\u9053\u4f60\u5728\u8bf4\u4ec0\u4e48\u3002<br \/>\n\u597d\u4e86\uff0c\u4ece\u4e0a\u9762\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\u6b63\u5219\u8868\u8fbe\u5f0f\u4e2d\u7684\u4e24\u4e2a\u57fa\u672c\u7ed3\u6784\uff1a<\/p>\n<ul>\n<li>\u8fde\u7ed3 (Concatenation)\uff0c\u6bd4\u5982 bitch\uff0c\u7531b, i, t, c, h\u8fde\u63a5\u800c\u6210<\/li>\n<li>\u8054\u5408 (Union)\uff0c\u6bd4\u5982 y|k|cus\uff0c\u53ef\u4ee5\u8ba4\u4e3a\u662fy\u6216k\u6216\u8005cus<\/li>\n<\/ul>\n<p>\u4e0b\u9762\u662f\u7b2c\u4e09\u4e2a\u57fa\u672c\u7ed3\u6784\uff0c\u88ab\u79f0\u4e3a<a href=\"http:\/\/en.wikipedia.org\/wiki\/Kleene_star\">Kleene star<\/a>\u00a0(\u6216\u8005 Kleene \u95ed\u5305)\u7684\u3002\u56e0\u4e3a\u8fd9\u4e2a\u64cd\u4f5c\u662f<a href=\"http:\/\/en.wikipedia.org\/wiki\/Stephen_Kleene\" target=\"_blank\" rel=\"noopener noreferrer\">Stephen Cole Kleene<\/a>\u53d1\u660e\u7684\u3002\u554a\u554a\uff0c\u5176\u5b9e\u6b63\u5219\u8868\u8fbe\u5f0f\u8fd9\u4e2a\u4e1c\u897f\u5c31\u662fKleene\u53d1\u660e\u7684\u3002\u8fd9\u4e2a\u540c\u5b66\u771f\u662f\u975e\u5e38\u7684\u725bB\uff0c\u56e0\u4e3a\u4ed6\u662f\u66f4\u52a0\u725bB\u7684 \u963f\u9686\u4f50 &#8211; \u4e18\u5947 ( Alonzo Church )\u2014\u2014\u5386\u53f2\u4e0a\u548c\u963f\u5170 &#8211; \u56fe\u7075 ( Alan Turing ) \u5e76\u79f0\u7684\u4eba\u7269\u2014\u2014\u7684\u5b66\u751f\u3002\u6709\u591a\u725bB\u5462\uff0c\u8fd9\u4e2aKleene\u8fd8\u548c\u4ed6\u7684\u8001\u5e08\uff0c\u8fd8\u6709\u56fe\u7075\uff0c\u5c31\u9012\u5f52\u8bba\u53d1\u8868\u4e86\u8bba\u6587\uff0c\u5960\u5b9a\u4e86\u53ef\u8ba1\u7b97\u7406\u8bba\u7684\u6839\u57fa\u3002\u554a\u54c8\u54c8\u54c8\uff0c\u771f\u662f\u725bB\u554a\u3002<br \/>\n\u55ef\uff0c\u6240\u8c13Kleene Star\u7684\u4f8b\u5b50\u5c31\u662f\u8fd9\u6837\u7684\u3002<\/p>\n<ul>\n<li>Kleene Star\uff0c\u6bd4\u5982a*\uff0c\u53ef\u4ee5\u63a5\u53d7\u7a7a\u4e32\u548c\u82e5\u5e72\u4e2aa\u8fde\u7ed3\u7ec4\u6210\u7684\u4e32<\/li>\n<\/ul>\n<p>\u5f53\u7136\u54af\uff0c\u8fd8\u6709\u4e00\u4e9b\u522b\u7684\u64cd\u4f5c\uff0c\u6bd4\u5982\u6211\u4eec\u77e5\u9053\u7684+\uff0c?\uff0c\u96c6\u5408[]\u7b49\u7b49\uff0c\u4f46\u662f\u8fd9\u4e9b\u64cd\u4f5c\u90fd\u53ef\u4ee5\u901a\u8fc7\u4e0a\u9762\u4e09\u4e2a\u57fa\u672c\u64cd\u4f5c\u7684\u7ec4\u5408\u6765\u5b8c\u6210\u3002<br \/>\n\u6bd4\u5982+\uff0ca+\u53ef\u4ee5\u8ba4\u4e3a\u662faa*<\/p>\n<h3>\u4ec0\u4e48\u662fNFA\uff1f<\/h3>\n<p>\u8981\u8bf4NFA\u561b\uff0c\u6211\u5f97\u5148\u8bf4\u8bf4DFA\u3002\u6240\u8c13DFA\uff0c\u5c31\u662f<a href=\"http:\/\/en.wikipedia.org\/wiki\/Finite_state_machine\" target=\"_blank\" rel=\"noopener noreferrer\">Deterministic Finite state Automata<\/a>\u7684\u7b80\u79f0\u3002\u662f\u72b6\u6001\u673a\u7684\u4e00\u79cd\u3002\u901a\u4fd7\u7684\u8bf4\uff0c\u5c31\u662f\u4e00\u5927\u5806\u72b6\u6001\u7684\u96c6\u5408\uff0c\u91cc\u9762\u6709\u4e00\u4e2a\u521d\u59cb\u72b6\u6001\u548c\u82e5\u5e72\u7ec8\u6b62\u72b6\u6001\uff0c\u6bcf\u4e2a\u72b6\u6001\u53ef\u4ee5\u6709\u82e5\u5e72\u4e2a\u8f93\u51fa\u8fb9\u524d\u5f80\u522b\u7684\u72b6\u6001\u3002\u4f46\u662f\u8981\u6c42\u6bcf\u4e2a\u72b6\u6001\u7684\u540c\u4e00\u79cd\u8f93\u51fa\u8fb9\u81f3\u591a\u53ea\u6709\u4e00\u4e2a\uff0c\u6240\u4ee5\u81ea\u52a8\u673a\u88ab\u79f0\u4e3a\u662f\u201dDeterministic\u201d\u7684\u3002<br \/>\n\u6bd4\u5982\u4e0b\u9762\u8fd9\u4e2a\u4f8b\u5b50\uff1a<br \/>\n\u8868\u8ff0\u7684\u662f\u4e00\u4e2a\u7535\u706fde\u5f00\u5173\uff0c\u8fd9\u4e2a\u5f00\u5173\u6bcf\u6309\u4e00\u4e0b\u5c31\u4ece\u2019\u5f00\u2019\u72b6\u6001\u8f6c\u6362\u5230\u2019\u5173\u2019\u72b6\u6001\uff0c\u6216\u8005\u4ece\u2019\u5173\u2019\u72b6\u6001\u8f6c\u6362\u5230\u2019\u5f00\u2019\u72b6\u6001\u3002\u800c\u4e3a\u4e86\u4ece\u73af\u4fdd\u89d2\u5ea6\u51fa\u53d1\uff0c\u5728\u2019\u5173\u2019\u72b6\u6001\u624d\u88ab\u8ba4\u4e3a\u662f\u7ec8\u6b62\u6001\u3002<br \/>\n<a href=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_1.png\"><img loading=\"lazy\" decoding=\"async\" title=\"dfa\" alt=\"dfa\" src=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_1.png\" width=\"387\" height=\"88\" \/><\/a><br \/>\n\u4e0a\u9762\u7684\u81ea\u52a8\u673a\u5462\uff0c\u5c31\u53ef\u4ee5\u63cf\u8ff0\u8fd9\u4e2a\u706f\u6ce1\u7684\u884c\u4e3a\u6a21\u5f0f\uff0c\u6216\u8005\u8bf4\u53ef\u4ee5\u63cf\u8ff0\u7535\u706f\u7684\u72b6\u6001\u8f6c\u6362\u8fc7\u7a0b\u3002\u8f93\u51fa\u8fb9\u5c31\u662f\u2019\u5f00\u2019\u6216\u8005\u2019\u5173\u2019\u7684\u52a8\u4f5c\uff0c\u6216\u8005\u8bf4\u8fd9\u4e2a\u706f\u6ce1\u7684\u5f00\u5173\uff0c\u53ea\u63a5\u53d7\u8fd9\u4e24\u79cd\u52a8\u4f5c\uff1a\u201cTrun On\u201d\uff0c\u201cTrun Off\u201d\u3002\u800c\u201dTrun On\u201d\u52a8\u4f5c\u53ea\u4f1a\u5bfc\u81f4\u706f\u7684\u72b6\u6001\u53d8\u6210\u201cOn\u201d\uff0c\u201cTrun Off\u201d\u52a8\u4f5c\u53ea\u4f1a\u5bfc\u81f4\u706f\u7684\u72b6\u6001\u53d8\u6210\u201cOff\u201d\uff0c\u8fd9\u662f\u786e\u5b9a\u7684\uff0c\u4f60\u7684\u5916\u5a46\u90fd\u53ef\u4ee5\u9884\u6599\u5230\u7684\u3002\u6240\u4ee5\u8bf4DFA\u662f\u786e\u5b9a\u6709\u9650\u72b6\u6001\u81ea\u52a8\u673a\u3002<br \/>\n\u73b0\u5728\u53ef\u4ee5\u8bf4NFA\u4e86\u3002\u8fd9\u4e2aNFA\u561b\uff0c\u5168\u79f0\u662fNon-deterministic Finite state Automata\u3002\u4e5f\u662f\u72b6\u6001\u81ea\u52a8\u673a\u7684\u4e00\u79cd\u3002\u786e\u5207\u5730\u8bf4\uff0c\u521a\u624d\u7684DFA\u662fNFA\u7684\u4e00\u4e2a\u5b50\u96c6\u3002\u548cDFA\u552f\u4e00\u7684\u533a\u522b\u5c31\u662f\u4ed6\u662f\u201dNon-deterministic\u201d\u7684\uff0c\u54c8\uff0c\u975e\u786e\u5b9a\u7684\uff0c\u6bcf\u4e2a\u72b6\u6001\u7684\u540c\u4e00\u79cd\u8f93\u51fa\u8fb9\u53ef\u4ee5\u4e0d\u6b62\u4e00\u4e2a\u3002<br \/>\n\u8fd8\u662f\u7528\u521a\u624d\u7684\u4f8b\u5b50\u3002\u73b0\u5728\u5047\u8bbe\u6211\u4eec\u7684\u7535\u706f\u6709\u4e00\u79cd\u65b0\u7684\u72b6\u6001\u54af\uff5e\uff1a\u574f\u6389\u4e86\u3002\u706f\u4e1d\u88ab\u8fc7\u5927\u7684\u7535\u6d41\u70e7\u65ad\u4e86\uff0c\u542c\u4e0a\u53bb\u906d\u900f\u4e86\uff0c\u56e0\u4e3a\u4e00\u201dTrun On\u201d\u5c31\u5f97\u51c6\u5907\u6362\u706f\u6ce1\u4e86\uff1a<br \/>\n<a href=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_2.png\"><img loading=\"lazy\" decoding=\"async\" title=\"nfa\" alt=\"nfa\" src=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_2.png\" width=\"427\" height=\"197\" \/><\/a><br \/>\n\u4f46\u662f\u6211\u4eec\u6ca1\u6cd5\u786e\u5b9a\u7684\u77e5\u9053\u54ea\u4e00\u6b21Trun On\u4f1a\u5bfc\u81f4\u706f\u6ce1\u574f\u6389\uff0c\u4f7f\u5f97\u706f\u6ce1\u8fdb\u5165\u201dDown\u201d\u72b6\u6001\u7684\u90a3\u6b21\u201c\u5f00\u201d\u64cd\u4f5c\u770b\u4e0a\u53bb\u8ddf\u4f60\u6628\u5929\u5f00\u706f\u7684\u90a3\u6b21\u64cd\u4f5c\u4e00\u6a21\u4e00\u6837\uff08\u4e25\u683c\u7684\u8bf4\uff0c\u6bcf\u4e00\u6b21\u70b9\u4eae\u706f\u6ce1\u90fd\u4f1a\u5bfc\u81f4\u706f\u4e1d\u7684\u72b6\u6001\u53d1\u751f\u53d8\u5316\uff0c\u4f46\u662f\u5728\u6b64\u7b80\u5316\u4e86\uff09<br \/>\n\u6240\u4ee5\u4ece\u72b6\u6001\u201dOff\u201d\u51fa\u6765\u7684\u8f93\u51fa\u8fb9\u4e2d\uff0c\u201dTrun On\u201d\u6709\u4e24\u6761\uff0c\u8fd9\u5c31\u5bfc\u81f4\u6ca1\u6cd5\u6839\u636e\u5f53\u524d\u72b6\u6001\u548c\u8f93\u51fa\u8fb9\u786e\u5b9a\u4e0b\u4e00\u72b6\u6001\uff0c\u8fd9\u5c31\u662f\u4e3a\u4ec0\u4e48\u79f0\u4e3a\u975e\u786e\u5b9a\u6027\u6709\u9650\u81ea\u52a8\u673a\u7684\u539f\u56e0\u3002<\/p>\n<h3>\u5982\u4f55\u8f6c\u6362\uff1f<\/h3>\n<p>\u521a\u624d<a href=\"http:\/\/www.sxnsx.com\/\">Shellex<\/a>\u8bf4\u4e86\uff0c\u6b63\u5219\u8868\u8fbe\u5f0f\u6709\u4e09\u79cd\u57fa\u672c\u7ed3\u6784\u3002\u5982\u679c\u80fd\u5148\u5c06\u8fd9\u4e09\u79cd\u57fa\u672c\u7ed3\u6784\u8f6c\u6362\u6210\u5bf9\u5e94\u7684NFA\uff0c\u7136\u540e\u5728\u7528\u8fd9\u4e09\u79cd\u57fa\u672c\u7ed3\u6784\u53bb\u62fc\u88c5\u6210\u5b8c\u6574\u7684NFA\u662f\u4e0d\u662f\u5f88\u7701\u529b\u5462\uff1f<br \/>\n\u4e0b\u9762\u5c31\u662f\u4e09\u79cd\u57fa\u672c\u6b63\u5219\u8868\u8fbe\u5f0f\u7684NFA<br \/>\nab:<br \/>\n<a href=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_3.png\"><img loading=\"lazy\" decoding=\"async\" title=\"g_basic_a_concat_b_blog\" alt=\"g_basic_a_concat_b_blog\" src=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_3.png\" width=\"568\" height=\"77\" \/><\/a><br \/>\na*:<br \/>\n<a href=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_4.png\"><img decoding=\"async\" title=\"g_basic_a_star_blog\" alt=\"g_basic_a_star_blog\" src=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_4.png\" \/><\/a><br \/>\na|b:<br \/>\n<a href=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_5.png\"><img decoding=\"async\" title=\"g_basic_a_union_b_blog\" alt=\"g_basic_a_union_b_blog\" src=\"http:\/\/image3.360doc.com\/DownloadImg\/2009\/2\/19\/98111_2586955_5.png\" \/><\/a><br \/>\n\u91cc\u9762\u51fa\u73b0\u4e86\u4e00\u79cd\u53eb\u201cNone\u201d\u7684\u8fb9\u3002\u8fd9\u4e2a\u4e0d\u4ee3\u8868\u8fd9\u4e2a\u8fb9\u662f\u5b57\u9762\u4e0a\u7684\u201cNone\u201d\uff0c\u800c\u662f\u6307\u8fd9\u4e2a\u8fb9\u662f\u4e2a\u7a7a\u8fb9\u3002\u4e5f\u5c31\u662f\u8bf4\u4efb\u4f55\u201c\u52a8\u4f5c\u201d\u90fd\u53ef\u4ee5\u4ece\u8fd9\u4e2a\u8fb9\u8fdb\u5165\u4e0b\u4e00\u4e2a\u72b6\u6001\u3002\u5b83\u7684\u5b66\u540d\u53eb epsilon \u8fb9\uff0c\u4e00\u822c\u8868\u793a\u6210\u2019\u03b5\u2019\uff0c<a href=\"http:\/\/www.sxnsx.com\/\">Shellex<\/a>\u8fd9\u91cc\u8868\u793a\u6210\u201cNone\u201d\u4e86\u3002<br \/>\n\u4e0b\u9762\u6211\u4eec\u6765\u8003\u8651\u6b63\u5219\u8868\u8fbe\u5f0f\u5230NFA\u8f6c\u6362\u3002\u7ed9\u51fa\u4e00\u4e2a\u6b63\u5219\u4e32\u7684\u8f93\u5165\uff0c\u5f97\u5230\u4e00\u4e2aNFA\u7684\u8f93\u51fa\u3002\u88ab\u5e7f\u6cdb\u91c7\u7528\u7684\u662fThompson Algorithm\uff0c\u4e5f\u5c31\u662f\u6240\u8c13\u7684\u5b50\u96c6\u7b97\u6cd5\u3002\u8be5\u7b97\u6cd5\u7684\u53d1\u660e\u4eba\u5e94\u8be5\u5c31\u662f\u5199ed\u7f16\u8f91\u5668\u7684\u90a3\u4e2a<a href=\"http:\/\/en.wikipedia.org\/wiki\/Ken_Thompson\">Thompson\u5927\u725b<\/a>\u3002\u8be5\u7b97\u6cd5\u7684\u5b9e\u73b0\u548c\u7b97\u672f\u8868\u8fbe\u5f0f\u7684\u6c42\u503c\u975e\u5e38\u7684\u7c7b\u4f3c\uff0c\u9700\u8981\u4e00\u4e2a\u7b26\u53f7\u6808\u5b58\u653e\u64cd\u4f5c\u7b26\uff0c\u4e00\u4e2a\u81ea\u52a8\u673a\u6808\u5b58\u653e\u751f\u6210\u7684\u81ea\u52a8\u673a\u3002\u7b97\u6cd5\u7ed3\u675f\u540e\uff0c\u53ef\u4ee5\u4ece\u81ea\u52a8\u673a\u6808\u4e2dPop\u4e00\u4e2a\u6700\u7ec8\u7684\u7ed3\u679c\u3002<br \/>\n\u6bd4\u5982\u5bf9\u4e8e\u6b63\u5219\u8868\u8fbe\u5f0f(a|b)*cd\uff0c\u6c42\u503c\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n<div>\n<div>\n<pre>PUSH a To automaton stack\nPUSH b To automaton stack\nUNION\nSTAR\nPUSH c To automaton stack\nCONCAT\nPUSH d To automaton stack\nCONCAT\nPOP result<\/pre>\n<\/div>\n<\/div>\n<p>\u91cc\u9762\u7684UNION\uff0cSTAR \u548c CONCAT\u5c31\u662f\u4e09\u79cd\u57fa\u672c\u7ed3\u6784\u7684\u751f\u6210\u64cd\u4f5c\u4e86\u3002\u800c\u8fd9\u4e09\u79cd\u57fa\u672c\u64cd\u4f5c\u7684\u5b9e\u73b0\u662f\u8fd9\u6837\u7684\uff1a<br \/>\n<strong>Star\uff1a<\/strong><\/p>\n<div>\n<div>\n<pre>POP T from automaton stack\nCREATE state A, B\nADD transition from A to B with '\u03b5'\nADD transition from A to T.entry with '\u03b5'\nADD transition from T.exit to A with '\u03b5'\nADD transition from T.exit to B with '\u03b5'\nADD state A, B to T\nPUSH T to automaton stack<\/pre>\n<\/div>\n<\/div>\n<p><strong>Concat\uff1a<\/strong><\/p>\n<div>\n<div>\n<pre>POP F, S from automaton stack\nADD transition from F.exit to S.entry with '\u03b5'\nJOIN S to F\nSET F.exit = S.exit\nSET F.inputSet += S.inputSet\nPUSH F to automaton stack<\/pre>\n<\/div>\n<\/div>\n<p><strong>Union:<\/strong><\/p>\n<div>\n<div>\n<pre>POP F, S from automaton stack\nCREATE state A, B\nADD transition from A to F.entry with '\u03b5'\nADD transition from A to S.entry with '\u03b5'\nADD transition from T.exit to B with '\u03b5'\nADD transition from T.exit to B with '\u03b5'\nJOIN S to F\nADD state A, B to T\nSET F.exit = S.exit\nSET F.inputSet += S.inputSet\nPUSH F to automaton stack<\/pre>\n<\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<pre>\/*\u00a0Regular\u00a0expression\u00a0implementation.\n\u00a0*\u00a0Supports\u00a0only\u00a0(\u00a0|\u00a0)\u00a0*\u00a0+\u00a0?.\u00a0\u00a0No\u00a0escapes.\n\u00a0*\u00a0Compiles\u00a0to\u00a0NFA\u00a0and\u00a0then\u00a0simulates\u00a0NFA\n\u00a0*\u00a0using\u00a0Thompson's\u00a0algorithm.\n\u00a0*\n\u00a0*\u00a0See\u00a0also\u00a0http:\/\/swtch.com\/~rsc\/regexp\/\u00a0and\n\u00a0*\u00a0Thompson,\u00a0Ken.\u00a0\u00a0Regular\u00a0Expression\u00a0Search\u00a0Algorithm,\n\u00a0*\u00a0Communications\u00a0of\u00a0the\u00a0ACM\u00a011(6)\u00a0(June\u00a01968),\u00a0pp.\u00a0419-422.\n\u00a0*\u00a0\n\u00a0*\u00a0Copyright\u00a0(c)\u00a02007\u00a0Russ\u00a0Cox.\n\u00a0*\u00a0Can\u00a0be\u00a0distributed\u00a0under\u00a0the\u00a0MIT\u00a0license,\u00a0see\u00a0bottom\u00a0of\u00a0file.\n\u00a0*\/\n#include\u00a0&lt;stdio.h&gt;\n#include\u00a0&lt;stdlib.h&gt;\n#include\u00a0&lt;string.h&gt;\n#include\u00a0&lt;unistd.h&gt;\n\/*\n\u00a0*\u00a0Convert\u00a0infix\u00a0regexp\u00a0re\u00a0to\u00a0postfix\u00a0notation.\n\u00a0*\u00a0Insert\u00a0.\u00a0as\u00a0explicit\u00a0concatenation\u00a0operator.\n\u00a0*\u00a0Cheesy\u00a0parser,\u00a0return\u00a0static\u00a0buffer.\n\u00a0*\/\nchar*\nre2post(char\u00a0*re)\n{\n\tint\u00a0nalt,\u00a0natom;\n\tstatic\u00a0char\u00a0buf[8000];\n\tchar\u00a0*dst;\n\tstruct\u00a0{\n\t\tint\u00a0nalt;\n\t\tint\u00a0natom;\n\t}\u00a0paren[100],\u00a0*p;\n\tp\u00a0=\u00a0paren;\n\tdst\u00a0=\u00a0buf;\n\tnalt\u00a0=\u00a00;\n\tnatom\u00a0=\u00a00;\n\tif(strlen(re)\u00a0&gt;=\u00a0sizeof\u00a0buf\/2)\n\t\treturn\u00a0NULL;\n\tfor(;\u00a0*re;\u00a0re++){\n\t\tswitch(*re){\n\t\tcase\u00a0'(':\n\t\t\tif(natom\u00a0&gt;\u00a01){\n\t\t\t\t--natom;\n\t\t\t\t*dst++\u00a0=\u00a0'.';\n\t\t\t}\n\t\t\tif(p\u00a0&gt;=\u00a0paren+100)\n\t\t\t\treturn\u00a0NULL;\n\t\t\tp-&gt;nalt\u00a0=\u00a0nalt;\n\t\t\tp-&gt;natom\u00a0=\u00a0natom;\n\t\t\tp++;\n\t\t\tnalt\u00a0=\u00a00;\n\t\t\tnatom\u00a0=\u00a00;\n\t\t\tbreak;\n\t\tcase\u00a0'|':\n\t\t\tif(natom\u00a0==\u00a00)\n\t\t\t\treturn\u00a0NULL;\n\t\t\twhile(--natom\u00a0&gt;\u00a00)\n\t\t\t\t*dst++\u00a0=\u00a0'.';\n\t\t\tnalt++;\n\t\t\tbreak;\n\t\tcase\u00a0')':\n\t\t\tif(p\u00a0==\u00a0paren)\n\t\t\t\treturn\u00a0NULL;\n\t\t\tif(natom\u00a0==\u00a00)\n\t\t\t\treturn\u00a0NULL;\n\t\t\twhile(--natom\u00a0&gt;\u00a00)\n\t\t\t\t*dst++\u00a0=\u00a0'.';\n\t\t\tfor(;\u00a0nalt\u00a0&gt;\u00a00;\u00a0nalt--)\n\t\t\t\t*dst++\u00a0=\u00a0'|';\n\t\t\t--p;\n\t\t\tnalt\u00a0=\u00a0p-&gt;nalt;\n\t\t\tnatom\u00a0=\u00a0p-&gt;natom;\n\t\t\tnatom++;\n\t\t\tbreak;\n\t\tcase\u00a0'*':\n\t\tcase\u00a0'+':\n\t\tcase\u00a0'?':\n\t\t\tif(natom\u00a0==\u00a00)\n\t\t\t\treturn\u00a0NULL;\n\t\t\t*dst++\u00a0=\u00a0*re;\n\t\t\tbreak;\n\t\tdefault:\n\t\t\tif(natom\u00a0&gt;\u00a01){\n\t\t\t\t--natom;\n\t\t\t\t*dst++\u00a0=\u00a0'.';\n\t\t\t}\n\t\t\t*dst++\u00a0=\u00a0*re;\n\t\t\tnatom++;\n\t\t\tbreak;\n\t\t}\n\t}\n\tif(p\u00a0!=\u00a0paren)\n\t\treturn\u00a0NULL;\n\twhile(--natom\u00a0&gt;\u00a00)\n\t\t*dst++\u00a0=\u00a0'.';\n\tfor(;\u00a0nalt\u00a0&gt;\u00a00;\u00a0nalt--)\n\t\t*dst++\u00a0=\u00a0'|';\n\t*dst\u00a0=\u00a00;\n\treturn\u00a0buf;\n}\n\/*\n\u00a0*\u00a0Represents\u00a0an\u00a0NFA\u00a0state\u00a0plus\u00a0zero\u00a0or\u00a0one\u00a0or\u00a0two\u00a0arrows\u00a0exiting.\n\u00a0*\u00a0if\u00a0c\u00a0==\u00a0Match,\u00a0no\u00a0arrows\u00a0out;\u00a0matching\u00a0state.\n\u00a0*\u00a0If\u00a0c\u00a0==\u00a0Split,\u00a0unlabeled\u00a0arrows\u00a0to\u00a0out\u00a0and\u00a0out1\u00a0(if\u00a0!=\u00a0NULL).\n\u00a0*\u00a0If\u00a0c\u00a0&lt;\u00a0256,\u00a0labeled\u00a0arrow\u00a0with\u00a0character\u00a0c\u00a0to\u00a0out.\n\u00a0*\/\nenum\n{\n\tMatch\u00a0=\u00a0256,\n\tSplit\u00a0=\u00a0257\n};\ntypedef\u00a0struct\u00a0State\u00a0State;\nstruct\u00a0State\n{\n\tint\u00a0c;\n\tState\u00a0*out;\n\tState\u00a0*out1;\n\tint\u00a0lastlist;\n};\nState\u00a0matchstate\u00a0=\u00a0{\u00a0Match\u00a0};\t\/*\u00a0matching\u00a0state\u00a0*\/\nint\u00a0nstate;\n\/*\u00a0Allocate\u00a0and\u00a0initialize\u00a0State\u00a0*\/\nState*\nstate(int\u00a0c,\u00a0State\u00a0*out,\u00a0State\u00a0*out1)\n{\n\tState\u00a0*s;\n\tnstate++;\n\ts\u00a0=\u00a0malloc(sizeof\u00a0*s);\n\ts-&gt;lastlist\u00a0=\u00a00;\n\ts-&gt;c\u00a0=\u00a0c;\n\ts-&gt;out\u00a0=\u00a0out;\n\ts-&gt;out1\u00a0=\u00a0out1;\n\treturn\u00a0s;\n}\n\/*\n\u00a0*\u00a0A\u00a0partially\u00a0built\u00a0NFA\u00a0without\u00a0the\u00a0matching\u00a0state\u00a0filled\u00a0in.\n\u00a0*\u00a0Frag.start\u00a0points\u00a0at\u00a0the\u00a0start\u00a0state.\n\u00a0*\u00a0Frag.out\u00a0is\u00a0a\u00a0list\u00a0of\u00a0places\u00a0that\u00a0need\u00a0to\u00a0be\u00a0set\u00a0to\u00a0the\n\u00a0*\u00a0next\u00a0state\u00a0for\u00a0this\u00a0fragment.\n\u00a0*\/\ntypedef\u00a0struct\u00a0Frag\u00a0Frag;\ntypedef\u00a0union\u00a0Ptrlist\u00a0Ptrlist;\nstruct\u00a0Frag\n{\n\tState\u00a0*start;\n\tPtrlist\u00a0*out;\n};\n\/*\u00a0Initialize\u00a0Frag\u00a0struct.\u00a0*\/\nFrag\nfrag(State\u00a0*start,\u00a0Ptrlist\u00a0*out)\n{\n\tFrag\u00a0n\u00a0=\u00a0{\u00a0start,\u00a0out\u00a0};\n\treturn\u00a0n;\n}\n\/*\n\u00a0*\u00a0Since\u00a0the\u00a0out\u00a0pointers\u00a0in\u00a0the\u00a0list\u00a0are\u00a0always\u00a0\n\u00a0*\u00a0uninitialized,\u00a0we\u00a0use\u00a0the\u00a0pointers\u00a0themselves\n\u00a0*\u00a0as\u00a0storage\u00a0for\u00a0the\u00a0Ptrlists.\n\u00a0*\/\nunion\u00a0Ptrlist\n{\n\tPtrlist\u00a0*next;\n\tState\u00a0*s;\n};\n\/*\u00a0Create\u00a0singleton\u00a0list\u00a0containing\u00a0just\u00a0outp.\u00a0*\/\nPtrlist*\nlist1(State\u00a0**outp)\n{\n\tPtrlist\u00a0*l;\n\tl\u00a0=\u00a0(Ptrlist*)outp;\n\tl-&gt;next\u00a0=\u00a0NULL;\n\treturn\u00a0l;\n}\n\/*\u00a0Patch\u00a0the\u00a0list\u00a0of\u00a0states\u00a0at\u00a0out\u00a0to\u00a0point\u00a0to\u00a0start.\u00a0*\/\nvoid\npatch(Ptrlist\u00a0*l,\u00a0State\u00a0*s)\n{\n\tPtrlist\u00a0*next;\n\tfor(;\u00a0l;\u00a0l=next){\n\t\tnext\u00a0=\u00a0l-&gt;next;\n\t\tl-&gt;s\u00a0=\u00a0s;\n\t}\n}\n\/*\u00a0Join\u00a0the\u00a0two\u00a0lists\u00a0l1\u00a0and\u00a0l2,\u00a0returning\u00a0the\u00a0combination.\u00a0*\/\nPtrlist*\nappend(Ptrlist\u00a0*l1,\u00a0Ptrlist\u00a0*l2)\n{\n\tPtrlist\u00a0*oldl1;\n\toldl1\u00a0=\u00a0l1;\n\twhile(l1-&gt;next)\n\t\tl1\u00a0=\u00a0l1-&gt;next;\n\tl1-&gt;next\u00a0=\u00a0l2;\n\treturn\u00a0oldl1;\n}\n\/*\n\u00a0*\u00a0Convert\u00a0postfix\u00a0regular\u00a0expression\u00a0to\u00a0NFA.\n\u00a0*\u00a0Return\u00a0start\u00a0state.\n\u00a0*\/\nState*\npost2nfa(char\u00a0*postfix)\n{\n\tchar\u00a0*p;\n\tFrag\u00a0stack[1000],\u00a0*stackp,\u00a0e1,\u00a0e2,\u00a0e;\n\tState\u00a0*s;\n\t\/\/\u00a0fprintf(stderr,\u00a0\"postfix:\u00a0%sn\",\u00a0postfix);\n\tif(postfix\u00a0==\u00a0NULL)\n\t\treturn\u00a0NULL;\n\t#define\u00a0push(s)\u00a0*stackp++\u00a0=\u00a0s\n\t#define\u00a0pop()\u00a0*--stackp\n\tstackp\u00a0=\u00a0stack;\n\tfor(p=postfix;\u00a0*p;\u00a0p++){\n\t\tswitch(*p){\n\t\tdefault:\n\t\t\ts\u00a0=\u00a0state(*p,\u00a0NULL,\u00a0NULL);\n\t\t\tpush(frag(s,\u00a0list1(&amp;s-&gt;out)));\n\t\t\tbreak;\n\t\tcase\u00a0'.':\t\/*\u00a0catenate\u00a0*\/\n\t\t\te2\u00a0=\u00a0pop();\n\t\t\te1\u00a0=\u00a0pop();\n\t\t\tpatch(e1.out,\u00a0e2.start);\n\t\t\tpush(frag(e1.start,\u00a0e2.out));\n\t\t\tbreak;\n\t\tcase\u00a0'|':\t\/*\u00a0alternate\u00a0*\/\n\t\t\te2\u00a0=\u00a0pop();\n\t\t\te1\u00a0=\u00a0pop();\n\t\t\ts\u00a0=\u00a0state(Split,\u00a0e1.start,\u00a0e2.start);\n\t\t\tpush(frag(s,\u00a0append(e1.out,\u00a0e2.out)));\n\t\t\tbreak;\n\t\tcase\u00a0'?':\t\/*\u00a0zero\u00a0or\u00a0one\u00a0*\/\n\t\t\te\u00a0=\u00a0pop();\n\t\t\ts\u00a0=\u00a0state(Split,\u00a0e.start,\u00a0NULL);\n\t\t\tpush(frag(s,\u00a0append(e.out,\u00a0list1(&amp;s-&gt;out1))));\n\t\t\tbreak;\n\t\tcase\u00a0'*':\t\/*\u00a0zero\u00a0or\u00a0more\u00a0*\/\n\t\t\te\u00a0=\u00a0pop();\n\t\t\ts\u00a0=\u00a0state(Split,\u00a0e.start,\u00a0NULL);\n\t\t\tpatch(e.out,\u00a0s);\n\t\t\tpush(frag(s,\u00a0list1(&amp;s-&gt;out1)));\n\t\t\tbreak;\n\t\tcase\u00a0'+':\t\/*\u00a0one\u00a0or\u00a0more\u00a0*\/\n\t\t\te\u00a0=\u00a0pop();\n\t\t\ts\u00a0=\u00a0state(Split,\u00a0e.start,\u00a0NULL);\n\t\t\tpatch(e.out,\u00a0s);\n\t\t\tpush(frag(e.start,\u00a0list1(&amp;s-&gt;out1)));\n\t\t\tbreak;\n\t\t}\n\t}\n\te\u00a0=\u00a0pop();\n\tif(stackp\u00a0!=\u00a0stack)\n\t\treturn\u00a0NULL;\n\tpatch(e.out,\u00a0&amp;matchstate);\n\treturn\u00a0e.start;\n#undef\u00a0pop\n#undef\u00a0push\n}\ntypedef\u00a0struct\u00a0List\u00a0List;\nstruct\u00a0List\n{\n\tState\u00a0**s;\n\tint\u00a0n;\n};\nList\u00a0l1,\u00a0l2;\nstatic\u00a0int\u00a0listid;\nvoid\u00a0addstate(List*,\u00a0State*);\nvoid\u00a0step(List*,\u00a0int,\u00a0List*);\n\/*\u00a0Compute\u00a0initial\u00a0state\u00a0list\u00a0*\/\nList*\nstartlist(State\u00a0*start,\u00a0List\u00a0*l)\n{\n\tl-&gt;n\u00a0=\u00a00;\n\tlistid++;\n\taddstate(l,\u00a0start);\n\treturn\u00a0l;\n}\n\/*\u00a0Check\u00a0whether\u00a0state\u00a0list\u00a0contains\u00a0a\u00a0match.\u00a0*\/\nint\nismatch(List\u00a0*l)\n{\n\tint\u00a0i;\n\tfor(i=0;\u00a0i&lt;l-&gt;n;\u00a0i++)\n\t\tif(l-&gt;s[i]\u00a0==\u00a0&amp;matchstate)\n\t\t\treturn\u00a01;\n\treturn\u00a00;\n}\n\/*\u00a0Add\u00a0s\u00a0to\u00a0l,\u00a0following\u00a0unlabeled\u00a0arrows.\u00a0*\/\nvoid\naddstate(List\u00a0*l,\u00a0State\u00a0*s)\n{\n\tif(s\u00a0==\u00a0NULL\u00a0||\u00a0s-&gt;lastlist\u00a0==\u00a0listid)\n\t\treturn;\n\ts-&gt;lastlist\u00a0=\u00a0listid;\n\tif(s-&gt;c\u00a0==\u00a0Split){\n\t\t\/*\u00a0follow\u00a0unlabeled\u00a0arrows\u00a0*\/\n\t\taddstate(l,\u00a0s-&gt;out);\n\t\taddstate(l,\u00a0s-&gt;out1);\n\t\treturn;\n\t}\n\tl-&gt;s[l-&gt;n++]\u00a0=\u00a0s;\n}\n\/*\n\u00a0*\u00a0Step\u00a0the\u00a0NFA\u00a0from\u00a0the\u00a0states\u00a0in\u00a0clist\n\u00a0*\u00a0past\u00a0the\u00a0character\u00a0c,\n\u00a0*\u00a0to\u00a0create\u00a0next\u00a0NFA\u00a0state\u00a0set\u00a0nlist.\n\u00a0*\/\nvoid\nstep(List\u00a0*clist,\u00a0int\u00a0c,\u00a0List\u00a0*nlist)\n{\n\tint\u00a0i;\n\tState\u00a0*s;\n\tlistid++;\n\tnlist-&gt;n\u00a0=\u00a00;\n\tfor(i=0;\u00a0i&lt;clist-&gt;n;\u00a0i++){\n\t\ts\u00a0=\u00a0clist-&gt;s[i];\n\t\tif(s-&gt;c\u00a0==\u00a0c)\n\t\t\taddstate(nlist,\u00a0s-&gt;out);\n\t}\n}\n\/*\u00a0Run\u00a0NFA\u00a0to\u00a0determine\u00a0whether\u00a0it\u00a0matches\u00a0s.\u00a0*\/\nint\nmatch(State\u00a0*start,\u00a0char\u00a0*s)\n{\n\tint\u00a0i,\u00a0c;\n\tList\u00a0*clist,\u00a0*nlist,\u00a0*t;\n\tclist\u00a0=\u00a0startlist(start,\u00a0&amp;l1);\n\tnlist\u00a0=\u00a0&amp;l2;\n\tfor(;\u00a0*s;\u00a0s++){\n\t\tc\u00a0=\u00a0*s\u00a0&amp;\u00a00xFF;\n\t\tstep(clist,\u00a0c,\u00a0nlist);\n\t\tt\u00a0=\u00a0clist;\u00a0clist\u00a0=\u00a0nlist;\u00a0nlist\u00a0=\u00a0t;\t\/*\u00a0swap\u00a0clist,\u00a0nlist\u00a0*\/\n\t}\n\treturn\u00a0ismatch(clist);\n}\nint\nmain(int\u00a0argc,\u00a0char\u00a0**argv)\n{\n\tint\u00a0i;\n\tchar\u00a0*post;\n\tState\u00a0*start;\n\tif(argc\u00a0&lt;\u00a03){\n\t\tfprintf(stderr,\u00a0\"usage:\u00a0nfa\u00a0regexp\u00a0string...n\");\n\t\treturn\u00a01;\n\t}\n\tpost\u00a0=\u00a0re2post(argv[1]);\n\tif(post\u00a0==\u00a0NULL){\n\t\tfprintf(stderr,\u00a0\"bad\u00a0regexp\u00a0%sn\",\u00a0argv[1]);\n\t\treturn\u00a01;\n\t}\n\tstart\u00a0=\u00a0post2nfa(post);\n\tif(start\u00a0==\u00a0NULL){\n\t\tfprintf(stderr,\u00a0\"error\u00a0in\u00a0post2nfa\u00a0%sn\",\u00a0post);\n\t\treturn\u00a01;\n\t}\n\tl1.s\u00a0=\u00a0malloc(nstate*sizeof\u00a0l1.s[0]);\n\tl2.s\u00a0=\u00a0malloc(nstate*sizeof\u00a0l2.s[0]);\n\tfor(i=2;\u00a0i&lt;argc;\u00a0i++)\n\t\tif(match(start,\u00a0argv[i]))\n\t\t\tprintf(\"%sn\",\u00a0argv[i]);\n\treturn\u00a00;\n}\n\/*\n\u00a0*\u00a0Permission\u00a0is\u00a0hereby\u00a0granted,\u00a0free\u00a0of\u00a0charge,\u00a0to\u00a0any\u00a0person\n\u00a0*\u00a0obtaining\u00a0a\u00a0copy\u00a0of\u00a0this\u00a0software\u00a0and\u00a0associated\n\u00a0*\u00a0documentation\u00a0files\u00a0(the\u00a0\"Software\"),\u00a0to\u00a0deal\u00a0in\u00a0the\n\u00a0*\u00a0Software\u00a0without\u00a0restriction,\u00a0including\u00a0without\u00a0limitation\n\u00a0*\u00a0the\u00a0rights\u00a0to\u00a0use,\u00a0copy,\u00a0modify,\u00a0merge,\u00a0publish,\u00a0distribute,\n\u00a0*\u00a0sublicense,\u00a0and\/or\u00a0sell\u00a0copies\u00a0of\u00a0the\u00a0Software,\u00a0and\u00a0to\n\u00a0*\u00a0permit\u00a0persons\u00a0to\u00a0whom\u00a0the\u00a0Software\u00a0is\u00a0furnished\u00a0to\u00a0do\u00a0so,\n\u00a0*\u00a0subject\u00a0to\u00a0the\u00a0following\u00a0conditions:\n\u00a0*\u00a0\n\u00a0*\u00a0The\u00a0above\u00a0copyright\u00a0notice\u00a0and\u00a0this\u00a0permission\u00a0notice\u00a0shall\n\u00a0*\u00a0be\u00a0included\u00a0in\u00a0all\u00a0copies\u00a0or\u00a0substantial\u00a0portions\u00a0of\u00a0the\n\u00a0*\u00a0Software.\n\u00a0*\u00a0\n\u00a0*\u00a0THE\u00a0SOFTWARE\u00a0IS\u00a0PROVIDED\u00a0\"AS\u00a0IS\",\u00a0WITHOUT\u00a0WARRANTY\u00a0OF\u00a0ANY\n\u00a0*\u00a0KIND,\u00a0EXPRESS\u00a0OR\u00a0IMPLIED,\u00a0INCLUDING\u00a0BUT\u00a0NOT\u00a0LIMITED\u00a0TO\u00a0THE\n\u00a0*\u00a0WARRANTIES\u00a0OF\u00a0MERCHANTABILITY,\u00a0FITNESS\u00a0FOR\u00a0A\u00a0PARTICULAR\n\u00a0*\u00a0PURPOSE\u00a0AND\u00a0NONINFRINGEMENT.\u00a0\u00a0IN\u00a0NO\u00a0EVENT\u00a0SHALL\u00a0THE\u00a0AUTHORS\n\u00a0*\u00a0OR\u00a0COPYRIGHT\u00a0HOLDERS\u00a0BE\u00a0LIABLE\u00a0FOR\u00a0ANY\u00a0CLAIM,\u00a0DAMAGES\u00a0OR\n\u00a0*\u00a0OTHER\u00a0LIABILITY,\u00a0WHETHER\u00a0IN\u00a0AN\u00a0ACTION\u00a0OF\u00a0CONTRACT,\u00a0TORT\u00a0OR\n\u00a0*\u00a0OTHERWISE,\u00a0ARISING\u00a0FROM,\u00a0OUT\u00a0OF\u00a0OR\u00a0IN\u00a0CONNECTION\u00a0WITH\u00a0THE\n\u00a0*\u00a0SOFTWARE\u00a0OR\u00a0THE\u00a0USE\u00a0OR\u00a0OTHER\u00a0DEALINGS\u00a0IN\u00a0THE\u00a0SOFTWARE.\n\u00a0*\/<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u6587\u7ae0\u6765\u81eahttp:\/\/www.360doc.com\/content\/09\/0219\/10\/98111_2586955.shtml \u4ee5\u53cahttp:\/\/hi.baidu.com\/tcet030840zxp\/item\/c923fe885ddd0329100ef3ec \u6700\u8fd1\u5f97\u505a\u4e00\u4e9b\u8ddf\u81ea\u52a8\u673a\u6709\u5173\u7684\u4e1c\u4e1c\uff0c\u5176\u4e2d\u4e00\u90e8\u5206\u53ef\u4ee5\u7b80\u8981\u5730\u770b\u4f5c\u662f\u7531\u4e00\u5957\u6b63\u5219\u6587\u6cd5\u751f\u6210\u72b6\u6001\u81ea\u52a8\u673a\u7684\u8fc7\u7a0b\u3002 \u4ec0\u4e48\u662f\u6b63\u5219\u8868\u8fbe\u5f0f\uff1f \u9996\u5148\u6211\u4eec\u770b\u770b\u4ec0\u4e48\u662f\u6b63\u5219\u8868\u8fbe\u5f0f\u3002\u8fd9\u4e2a\u4e1c\u4e1c\u5462\uff0c\u4e00\u822c\u7528\u4e8e\u63cf\u8ff0\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684\u96c6\u5408\u2014\u2014\u76f4\u63a5\u8bf4\u5c31\u662f\u4e00\u4e2a\u6b63\u5219\u8868\u8fbe\u5f0f\u53ef\u80fd\u53ef\u4ee5\u5339\u914d\u4e00\u5927\u5806\u5b57\u7b26\u4e32\uff0c\u800c\u8fd9\u4e00\u5927\u5806\u5b57\u7b26\u4e32\u53ef\u4ee5\u5f62\u6210\u4e00\u4e2a\u96c6\u5408\uff0c\u5b83\u4eec\u7684\u5171\u540c\u7279\u5f81\u5c31\u662f\u53ef\u4ee5\u88ab\u8fd9\u4e2a\u6b63\u5219\u8868\u8fbe\u5f0f\u5339\u914d\u3002\u5c31\u50cf\u53bb\u6b7b\u53bb\u6b7b\u56e2\uff0c\u4f46\u662f\u4e0d\u540c\u7684\u662f\u53bb\u6b7b\u53bb\u6b7b\u56e2\u7684\u56e2\u5458\u7684\u5171\u540c\u7279\u5f81\u662f\u4e0d\u88ab\u4efb\u4f55\u5f02\u6027\u6240\u5339\u914d\u2014\u2014\u4f46\u662f\u8fd9\u6ca1\u5173\u7cfb\uff0c\u6211\u4eec\u4e0d\u59a8\u53d6\u53bb\u6b7b\u53bb\u6b7b\u56e2\u7684\u8865\u96c6\u5c31\u884c\u4e86\u3002 \u53cd\u6b63\u6b63\u5219\u8868\u8fbe\u662f\u5f88\u597d\u5566\uff0c\u56e0\u4e3a\u4f60\u53ea\u8981\u7528\u4e00\u70b9\u70b9\u5728\u810f\u8bdd\u91cc\uff0c\u5c31\u53ef\u4ee5\u9a82\u597d\u591a\u597d\u591a\u4eba\uff0c\u6bd4\u5982\uff1a Mar(y|k|cus) is son of bitch. \u771f\u662f\u975e\u5e38de\u7701\u529b\uff0c\u552f\u4e00\u7684\u7f3a\u70b9\u662f\u53ef\u80fd\u5bf9\u65b9\u4e0d\u77e5\u9053\u4f60\u5728\u8bf4\u4ec0\u4e48\u3002 \u597d\u4e86\uff0c\u4ece\u4e0a\u9762\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\u6b63\u5219\u8868\u8fbe\u5f0f\u4e2d\u7684\u4e24\u4e2a\u57fa\u672c\u7ed3\u6784\uff1a \u8fde\u7ed3 (Concatenation)\uff0c\u6bd4\u5982 bitch\uff0c\u7531b, i, t, c, h\u8fde\u63a5\u800c\u6210 \u8054\u5408 (Union)\uff0c\u6bd4\u5982 y|k|cus\uff0c\u53ef\u4ee5\u8ba4\u4e3a\u662fy\u6216k\u6216\u8005cus \u4e0b\u9762\u662f\u7b2c\u4e09\u4e2a\u57fa\u672c\u7ed3\u6784\uff0c\u88ab\u79f0\u4e3aKleene star\u00a0(\u6216\u8005 Kleene \u95ed\u5305)\u7684\u3002\u56e0\u4e3a\u8fd9\u4e2a\u64cd\u4f5c\u662fStephen Cole Kleene\u53d1\u660e\u7684\u3002\u554a\u554a\uff0c\u5176\u5b9e\u6b63\u5219\u8868\u8fbe\u5f0f\u8fd9\u4e2a\u4e1c\u897f\u5c31\u662fKleene\u53d1\u660e\u7684\u3002\u8fd9\u4e2a\u540c\u5b66\u771f\u662f\u975e\u5e38\u7684\u725bB\uff0c\u56e0\u4e3a\u4ed6\u662f\u66f4\u52a0\u725bB\u7684 \u963f\u9686\u4f50 &#8211; \u4e18\u5947 ( Alonzo Church )\u2014\u2014\u5386\u53f2\u4e0a\u548c\u963f\u5170 &#8211; \u56fe\u7075 ( Alan Turing ) \u5e76\u79f0\u7684\u4eba\u7269\u2014\u2014\u7684\u5b66\u751f\u3002\u6709\u591a\u725bB\u5462\uff0c\u8fd9\u4e2aKleene\u8fd8\u548c\u4ed6\u7684\u8001\u5e08\uff0c\u8fd8\u6709\u56fe\u7075\uff0c\u5c31\u9012\u5f52\u8bba\u53d1\u8868\u4e86\u8bba\u6587\uff0c\u5960\u5b9a\u4e86\u53ef\u8ba1\u7b97\u7406\u8bba\u7684\u6839\u57fa\u3002\u554a\u54c8\u54c8\u54c8\uff0c\u771f\u662f\u725bB\u554a\u3002 \u55ef\uff0c\u6240\u8c13Kleene Star\u7684\u4f8b\u5b50\u5c31\u662f\u8fd9\u6837\u7684\u3002 Kleene Star\uff0c\u6bd4\u5982a*\uff0c\u53ef\u4ee5\u63a5\u53d7\u7a7a\u4e32\u548c\u82e5\u5e72\u4e2aa\u8fde\u7ed3\u7ec4\u6210\u7684\u4e32 \u5f53\u7136\u54af\uff0c\u8fd8\u6709\u4e00\u4e9b\u522b\u7684\u64cd\u4f5c\uff0c\u6bd4\u5982\u6211\u4eec\u77e5\u9053\u7684+\uff0c?\uff0c\u96c6\u5408[]\u7b49\u7b49\uff0c\u4f46\u662f\u8fd9\u4e9b\u64cd\u4f5c\u90fd\u53ef\u4ee5\u901a\u8fc7\u4e0a\u9762\u4e09\u4e2a\u57fa\u672c\u64cd\u4f5c\u7684\u7ec4\u5408\u6765\u5b8c\u6210\u3002 \u6bd4\u5982+\uff0ca+\u53ef\u4ee5\u8ba4\u4e3a\u662faa* \u4ec0\u4e48\u662fNFA\uff1f \u8981\u8bf4NFA\u561b\uff0c\u6211\u5f97\u5148\u8bf4\u8bf4DFA\u3002\u6240\u8c13DFA\uff0c\u5c31\u662fDeterministic Finite state Automata\u7684\u7b80\u79f0\u3002\u662f\u72b6\u6001\u673a\u7684\u4e00\u79cd\u3002\u901a\u4fd7\u7684\u8bf4\uff0c\u5c31\u662f\u4e00\u5927\u5806\u72b6\u6001\u7684\u96c6\u5408\uff0c\u91cc\u9762\u6709\u4e00\u4e2a\u521d\u59cb\u72b6\u6001\u548c\u82e5\u5e72\u7ec8\u6b62\u72b6\u6001\uff0c\u6bcf\u4e2a\u72b6\u6001\u53ef\u4ee5\u6709\u82e5\u5e72\u4e2a\u8f93\u51fa\u8fb9\u524d\u5f80\u522b\u7684\u72b6\u6001\u3002\u4f46\u662f\u8981\u6c42\u6bcf\u4e2a\u72b6\u6001\u7684\u540c\u4e00\u79cd\u8f93\u51fa\u8fb9\u81f3\u591a\u53ea\u6709\u4e00\u4e2a\uff0c\u6240\u4ee5\u81ea\u52a8\u673a\u88ab\u79f0\u4e3a\u662f\u201dDeterministic\u201d\u7684\u3002 \u6bd4\u5982\u4e0b\u9762\u8fd9\u4e2a\u4f8b\u5b50\uff1a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-246","post","type-post","status-publish","format-standard","hentry","category-study"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/246","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=246"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/246\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}