{"id":8059,"date":"2024-04-21T08:01:01","date_gmt":"2024-04-21T00:01:01","guid":{"rendered":""},"modified":"2024-04-21T08:01:01","modified_gmt":"2024-04-21T00:01:01","slug":"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b","status":"publish","type":"post","link":"https:\/\/mushiming.com\/8059.html","title":{"rendered":"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b"},"content":{"rendered":"<p><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"display: none;\"> \n <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path> \n<\/svg> <\/p>\n<h2>Part 1 \u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b<\/h2>\n<p><img decoding=\"async\" src=\"https:\/\/img.mushiming.top\/app\/mushiming_com\/7c02ce8f9f7842588857624dc004473c.png\" =\"\" =\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\" alt=\"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b (https:\/\/mushiming.com\/)  \u7b2c1\u5f20\" title=\"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b  \u7b2c1\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" ><br \/> <img decoding=\"async\" src=\"https:\/\/img.mushiming.top\/app\/mushiming_com\/b79f9c04b3904172a8c2b4b230f1949e.png\" =\"\" =\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\" alt=\"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b (https:\/\/mushiming.com\/)  \u7b2c2\u5f20\" title=\"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522b  \u7b2c2\u5f20-\u7a46\u4e16\u660e\u535a\u5ba2\" ><\/p>\n<h2>Part 2 \u6982\u5ff5<\/h2>\n<p>\u6587\u6cd5G=(V\uff0cT\uff0cP\uff0cS)<\/p>\n<p>G\u53eb\u505a0\u578b\u6587\u6cd5(type 0 grammar)\uff0c\u4e5f\u53eb\u505a\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5(phrase structure grammar, PSG)\u3002<\/p>\n<p>L(G)\u53eb\u505a0\u578b\u8bed\u8a00\u3002\u4e5f\u53ef\u4ee5\u53eb\u505a\u77ed\u8bed\u7ed3\u6784\u8bed\u8a00(PSL)\u3001\u9012\u5f52\u53ef\u679a\u4e3e\u96c6(recursively enumerable \uff0cr.e. )\u3002 \u5bf9\u5e94\u7684\u5176\u8bc6\u522b\u8bed\u8a00\u673a\u5668\u4e3a<mark>\u56fe\u7075\u673a(TM\uff1aturing machine)<\/mark><\/p>\n<p><mark>G\u662f0\u578b\u6587\u6cd5\u3002<\/mark><\/p>\n<p>\u5982\u679c\u5bf9\u4e8e\"\u03b1-&gt;\u03b2\u2208P\uff0c\u5747\u6709|\u03b2|\u2265|\u03b1|\u6210\u7acb\uff0c\u5219\u79f0G\u4e3a1\u578b\u6587\u6cd5(type 1 <\/p>\n","protected":false},"excerpt":{"rendered":"\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a\u4e0b\u6587\u6709\u5173\u6587\u6cd5\uff08CSG\uff09\u3001\u4e0a\u4e0b\u6587\u65e0\u5173\u6587\u6cd5\uff08CFG\uff09\u3001\u53f3\u7ebf\u6027\u6587\u6cd5(RLG)\u7684\u533a\u522bPart1\u77ed\u8bed\u7ed3\u6784\u6587\u6cd5\uff08PSG\uff09\u3001\u4e0a...","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8059"}],"collection":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/comments?post=8059"}],"version-history":[{"count":0,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/posts\/8059\/revisions"}],"wp:attachment":[{"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/media?parent=8059"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/categories?post=8059"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mushiming.com\/wp-json\/wp\/v2\/tags?post=8059"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}