{"id":282,"date":"2024-06-09T18:49:18","date_gmt":"2024-06-09T09:49:18","guid":{"rendered":"http:\/\/www.yanagichiaki.jp\/?p=282"},"modified":"2024-06-21T20:13:41","modified_gmt":"2024-06-21T11:13:41","slug":"flaa","status":"publish","type":"post","link":"https:\/\/yanagichiaki.jp\/index.php\/2024\/06\/09\/flaa\/","title":{"rendered":"\u5f62\u5f0f\u8a00\u8a9e\u3068\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3000\u629c\u7c8b\uff0b\u554f\u984c"},"content":{"rendered":"\n\n\n\n\n<h1 class=\"wp-block-heading\">0. \u7d39\u4ecb<\/h1>\n\n\n\n<p>Not now.<\/p>\n\n\n\n<h1 class=\"wp-block-heading\">1. \u5fc5\u8981\u306a\u77e5\u8b58<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">1.1 \u6982\u5ff5<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Name<\/td><td>Explanation<\/td><td>Sample<\/td><\/tr><tr><td>\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8<\/td><td>\u6587\u5b57\u306e\u975e\u7a7a\u6709\u9650\u96c6\u5408<\/td><td><strong>$\\Sigma = \\{a, b, c, \\cdots \\}$<\/strong><\/td><\/tr><tr><td>\u6587\u5b57\u5217<\/td><td>\u3042\u308b\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\u6709\u9650\u9577\u30b7\u30fc\u30b1\u30f3\u30b9<\/td><td><strong>$aabcab$<\/strong><\/td><\/tr><tr><td>\u6587\u5b57\u5217\u306e\u9577\u3055<\/td><td>\u6587\u5b57\u5217\u306e\u5b57\u6570<\/td><td>$aabcab$\u306e\u9577\u3055\u306f<strong>6<\/strong><\/td><\/tr><tr><td><strong>$\\varepsilon$<\/strong><\/td><td>\u7a7a\u6587\u5b57\u5217<\/td><td>\u9577\u3055\uff10\u306e\u6587\u5b57\u5217<\/td><\/tr><tr><td>\u6587\u5b57\u5217\u306e\u63a5\u7d9a<\/td><td>concatenate\u64cd\u4f5c\u3001\u30aa\u30da\u30ec\u30fc\u30bf\u30fc\u306f$\\cdot$<\/td><td><strong>$x\\cdot y = xy$, $x\\varepsilon=x$<\/strong><\/td><\/tr><tr><td>\u6587\u5b57\u5217\u306e\u30d9\u30ad<\/td><td>\u7e70\u308a\u8fd4\u3057\u63a5\u7d9a<\/td><td><strong>$x^3=xxx$,$x^0=\\varepsilon$,<br>$\\varepsilon^n = \\varepsilon$<\/strong><\/td><\/tr><tr><td>\u8a00\u8a9e<\/td><td>\u3042\u308b\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\u7279\u5b9a\u6587\u5b57\u5217\u96c6\u5408<\/td><td><strong>$L=\\{\\varepsilon,aa,bb,cc,\\cdots\\}$<\/strong><br><strong>$\\varnothing$,$\\{\\varepsilon\\}$<\/strong>\u306f\u4efb\u610f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\u8a00\u8a9e<\/td><\/tr><tr><td>\u8a00\u8a9e\u306e\u63a5\u7d9a<\/td><td>concatenate\u64cd\u4f5c\u3001\u30aa\u30da\u30ec\u30fc\u30bf\u30fc\u306f$\\cdot$<\/td><td><strong>$LR=\\{w=xy|x\\in L\\land y\\in R\\}$<\/strong><\/td><\/tr><tr><td>\u8a00\u8a9e\u306e\u30d9\u30ad<\/td><td>\u7e70\u308a\u8fd4\u3057\u63a5\u7d9a<\/td><td><strong>$L^2=\\{w=xy|x\\in L\\land y\\in L\\}$<br>$L^0=\\{\\varepsilon\\}$<\/strong><\/td><\/tr><tr><td>\u30af\u30ea\u30fc\u30cd\u9589\u5305<\/td><td>\u5168(*)\u9589\u5305\u3001\u53cd\u5c04\u63a8\u79fb\u9589\u5305<\/td><td><strong>$\\Sigma^*=\\bigcup\\limits_{i=0}^{\\infty}\\Sigma^i$<\/strong><\/td><\/tr><tr><td>\u6b63\u898f\u9589\u5305<\/td><td>\u6b63\u9589\u5305\u3001\u63a8\u79fb\u9589\u5305<\/td><td><strong>$\\Sigma^+=\\bigcup\\limits_{i=1}^{\\infty}\\Sigma^i$<\/strong><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">1.2 \u8af8\u6027\u8cea<\/h2>\n\n\n\n<p>$\\Sigma^*=\\{\\varepsilon\\}\\cup\\Sigma^+$<br>$\\varnothing^+=\\varnothing$<br>$\\varnothing^*=\\{\\varepsilon\\}$<br>$(L^+)^+=L^+$<br>$(L^*)^*=L^*$<br>$L^+ \\cup R^+ \\subseteq (L\\cup R)^+$<br>$L^* \\cup R^* \\subseteq (L\\cup R)^* = (L^*R^*)^*=  (R^*L^*)^*$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1.3 \u5c0f\u30c6\u30b9\u30c8<\/h2>\n\n\n\n<p>I.\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8 $\\Sigma= \\{a,b\\}$ \u3068\u3059\u308b\u3068\u3001\u30af\u30ea\u30fc\u30cd\u9589\u5305$\\Sigma^*$\u306e\u5143\u306e\u9577\u3055\u306f\uff3f\uff3f<\/p>\n\n\n\n<p>(A) 0\u3001\u6709\u9650\u6570\u3001\u307e\u305f\u306f\u7121\u9650\u5927\u3002<br>(B) \u7121\u9650\u5927\u306e\u307f<br>(C) \u7121\u9650\u5927\u307e\u305f\u306f\u6709\u9650\u6570<br>(D) \u6709\u9650\u6570\u306e\u307f<\/p>\n\n\n\n<p>II.\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\u30af\u30ea\u30fc\u30cd\u9589\u5305\u306f\u7121\u9650\u96c6\u5408\u3067\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3002<\/p>\n\n\n\n<p>(A) True<br>(B) False<\/p>\n\n\n\n<p>III.$\\forall\\Sigma(\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8$\\rightarrow \\Sigma^*\\neq \\Sigma^+)$<\/p>\n\n\n\n<p>(A) True<br>(B) False<\/p>\n\n\n\n<p>IV.$\\forall S(S$\u306f\u96c6\u5408$\\rightarrow S^*\\neq S^+)$<\/p>\n\n\n\n<p>(A) True<br>(B) False<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1.4 Answer<\/h2>\n\n\n\n<p>I.D<br>II.B<br>III.A<br>IV.B<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1.5 \u691c\u5b9a\u554f\u984c<\/h2>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>1.{$\\varepsilon$, 0, 00}\u306e\u51aa\u96c6\u5408\u3092\u6c42\u3081<\/p>\n<cite>$\\{\\varnothing, \\{\\varepsilon\\}, \\{0\\}, \\{00\\}, \\{\\varepsilon, 0\\}, \\{\\varepsilon, 00\\}, \\{0, 00\\}, \\{\\varepsilon, 0, 00\\}\\}$<\/cite><\/blockquote>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>2.\u6b21\u306e\u5f0f\u306e\u6b63\u8aa4\u3092\u5224\u65ad\u3002<br>(1) $(LR)^*=(RL)^*$<br>(2) $L^+=L^+L^+$<br>(3) $L^*=L^*L^*$<br>(4) $(L\\cup R)^*=R^*\\cup L^*$<br>(5) $(LR\\cup L)^*L=L(RL\\cup L)^*$<br>(6) $R(LR\\cup R)^*L=LL^*R(LL^*R)^*$<br>(7) $(L^+)^*=(L^*)^+=L^*$<br>(8) $L^*L^+=L^+L^*=L^+$<\/p>\n<cite>(1) False<br>(2) False<br>(3) True<br>(4) False<br>(5) True<br>(6) False<br>(7) True<br>(8) True<\/cite><\/blockquote>\n\n\n\n<h1 class=\"wp-block-heading\">2. \u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">2.1 \u6c7a\u5b9a\u7684\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h2>\n\n\n\n<p>$DFA=(Q,\\Sigma,\\delta,q_0,F)$<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$Q$\u306f\u72b6\u614b\u96c6\u5408\u3001$\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\delta$\u306f\u72b6\u614b\u9077\u79fb\u95a2\u6570\u3001$q_0$\u306f\u521d\u671f\u72b6\u614b\u3001$F$\u306f\u53d7\u7406\u72b6\u614b\u96c6\u5408\u3002<\/p>\n\n\n\n<p>$\\delta: Q\\times\\Sigma\\rightarrow Q$\u3002<\/p>\n\n\n\n<p>$L(M) = \\{w|\\hat\\delta(q_0,w)\\in F\\}$\u306f$M$\u306e\u53d7\u7406\u8a00\u8a9e\u3068\u3044\u3044\u3001\u307e\u305f\u306f$M$\u306e\u8a00\u8a9e\u3002<\/p>\n\n\n\n<p>DFA\u306e\u8a00\u8a9e\u306f\u6b63\u898f\u8a00\u8a9e\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<p>DFA\u3067\u3001\u4efb\u610f\u306e\u72b6\u614b\u306f\u4efb\u610f\u306e\u5165\u529b\u3078\u306e\u5bfe\u51e6\u3059\u3079\u304d\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.2 \u975e\u6c7a\u5b9a\u7684\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h2>\n\n\n\n<p>$NFA=(Q,\\Sigma,\\delta,q_0,F)$<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$Q$\u306f\u72b6\u614b\u96c6\u5408\u3001$\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\delta$\u306f\u72b6\u614b\u9077\u79fb\u95a2\u6570\u3001$q_0$\u306f\u521d\u671f\u72b6\u614b\u3001$F$\u306f\u53d7\u7406\u72b6\u614b\u96c6\u5408\u3002<\/p>\n\n\n\n<p>$\\delta: Q\\times\\Sigma\\rightarrow 2^Q$\u3002<\/p>\n\n\n\n<p>$L(M) = \\{w|\\hat\\delta(q_0,w)\\cap F\\neq\\varnothing\\}$\u306f$M$\u306e\u53d7\u7406\u8a00\u8a9e\u3068\u3044\u3044\u3001\u307e\u305f\u306f$M$\u306e\u8a00\u8a9e\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.3 DFA $\\leftrightarrow$ NFA<\/h2>\n\n\n\n<p>DFA\u3001NFA\u306f\u540c\u3058\u8a00\u8a9e\u8868\u73fe\u80fd\u529b\u3092\u6301\u3064\u2014\u2014\u6b63\u898f\u8a00\u8a9e\u3002<\/p>\n\n\n\n<p>\u307e\u305a\u3001DFA\u306f\u7279\u5225\u306aNFA\u3002<\/p>\n\n\n\n<p><strong>NFA\u304b\u3089DFA\u3078\u306e\u5909\u63db<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u521d\u671f\u72b6\u614b\u96c6\u5408\u304b\u3089\u3072\u3068\u3064\u305a\u3064\u3001NFA\u306e\u72b6\u614b\u96c6\u5408\u3092DFA\u306e\u72b6\u614b\u3078\u5909\u63db\u3002<\/strong><\/li>\n\n\n\n<li><strong>DFA\u72b6\u614b$\\varnothing$\u3092\u8a2d\u7f6e\u3057\u3001\u5fc5\u8981\u306a\u72b6\u614b\u9077\u79fb\u3092\u6dfb\u4ed8\u3002<\/strong><\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">2.4 \u03b5\u52d5\u4f5c\u4ed8\u304d\u975e\u6c7a\u5b9a\u7684\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h2>\n\n\n\n<p>$\\varepsilon NFA=(Q,\\Sigma,\\delta,q_0,F)$<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$Q$\u306f\u72b6\u614b\u96c6\u5408\u3001$\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\delta$\u306f\u72b6\u614b\u9077\u79fb\u95a2\u6570\u3001$q_0$\u306f\u521d\u671f\u72b6\u614b\u3001$F$\u306f\u53d7\u7406\u72b6\u614b\u96c6\u5408\u3002<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$\\delta: Q\\times(\\Sigma\\cup\\{\\varepsilon\\})\\rightarrow 2^Q$\u3002<\/p>\n\n\n\n<p>$L(M) = \\{w|\\hat\\delta(q_0,w)\\cap F\\neq\\varnothing\\}$\u306f$M$\u306e\u53d7\u7406\u8a00\u8a9e\u3068\u3044\u3044\u3001\u307e\u305f\u306f$M$\u306e\u8a00\u8a9e\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.5 <strong>\u03b5-NFA\u306e\u69cb\u9020\u30c6\u30f3\u30d7\u30ec\u30fc\u30c8<\/strong><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">2.5.1 \u6700\u5f8c\u306e 3 \u6587\u5b57\u306e\u3046\u3061\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f\u300c1\u300d<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" width=\"1024\" height=\"194\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-1024x194.png\" alt=\"\" class=\"wp-image-422\" style=\"width:449px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-1024x194.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-300x57.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-768x146.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-1536x291.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.1-1-2048x388.png 2048w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">2.5.2 \u6700\u521d\u306e 3 \u6587\u5b57\u306e\u3046\u3061\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f\u300c0\u300d<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" width=\"1024\" height=\"169\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1-1024x169.png\" alt=\"\" class=\"wp-image-423\" style=\"width:445px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1-1024x169.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1-300x49.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1-768x127.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1-1536x253.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.5.2-1.png 1964w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">2.6 DFA $\\leftrightarrow$ \u03b5-NFA<\/h2>\n\n\n\n<p>DFA\u3001NFA\u3001\u03b5-NFA\u306f\u540c\u3058\u8a00\u8a9e\u8868\u73fe\u80fd\u529b\u3092\u6301\u3064\u2014\u2014\u6b63\u898f\u8a00\u8a9e\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">2.6.1 \u03b5\u9589\u5305<\/h3>\n\n\n\n<p>\u3042\u308b\u72b6\u614b\u306e\u9589\u5305\u3068\u306f\u3001\u81ea\u4f53\u3092\u542b\u307f\u3001\u03b5\u52d5\u4f5c\u306b\u3088\u3063\u3066\u9077\u79fb\u3067\u304d\u308b\u72b6\u614b\u306e\u96c6\u5408\u3002<\/p>\n\n\n\n<p>2.5.1\u306e\u03b5\u9589\u5305<\/p>\n\n\n\n<p>$E(q_0)=\\{q_0\\}, E(q_1)=\\{q_1,q_2,q_3\\}$<br>$E(q_2)=\\{q_2,q_3\\}, E(q_3)=\\{q_3\\}$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>2.6.2 \u03b5-NFA\u304b\u3089DFA\u3078\u306e\u5909\u63db<\/strong><\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>\u8af8\u03b5-NFA\u72b6\u614b\u306e\u03b5\u9589\u5305\u3092\u6c42\u3081\u3002<\/strong><\/li>\n\n\n\n<li><strong>\u521d\u671f\u72b6\u614b\u96c6\u5408\u03b5\u9589\u5305\u304b\u3089\u3072\u3068\u3064\u305a\u3064\u3001\u03b5-NFA\u306e\u72b6\u614b\u96c6\u5408\u03b5\u9589\u5305\u3092DFA\u306e\u72b6\u614b\u3078\u5909\u63db\u3002<\/strong><\/li>\n\n\n\n<li><strong>DFA\u72b6\u614b$\\varnothing$\u3092\u8a2d\u7f6e\u3057\u3001\u5fc5\u8981\u306a\u72b6\u614b\u9077\u79fb\u3092\u6dfb\u4ed8\u3002<\/strong><\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">2.7 \u5c0f\u30c6\u30b9\u30c8<\/h2>\n\n\n\n<p>I.$\\Sigma=\\{0,1\\}$, $L=\\{w|01$\u306f$w$\u306e\u90e8\u5206\u6587\u5b57\u5217$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>II.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067\u3001$1$\u304c\u5076\u6570\u56de\u51fa\u73fe$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>III.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067\u3001$0,1$\u304c\u5076\u6570\u56de\u51fa\u73fe$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.$\\Sigma=\\{0,1\\}$, $L=\\{w|010$\u306f$w$\u306e\u90e8\u5206\u6587\u5b57\u5217$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>V.$\\Sigma=\\{0,1\\}$, $L=\\{w|010$\u306f$w$\u306e\u90e8\u5206\u6587\u5b57\u5217\u3067\u306f\u306a\u3044$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VI.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067\u3001$01$\u304c\u5947\u6570\u56de\u51fa\u73fe$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VII.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\land w $\u306e\u5168\u3066\u306e\u63a5\u982d\u90e8\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u5dee\u306e\u7d76\u5bfe\u5024$\\leq1\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064DFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VIII.$\\forall L(|L|&lt;\\aleph_0\\rightarrow L$\u306f\u6b63\u898f\u8a00\u8a9e$)$<\/p>\n\n\n\n<p>IX. $\\varnothing$, $\\{\\varepsilon\\}$\u306eDFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>X.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|\\geq 3\\land w $\u306e\u7b2c2\u6587\u5b57$\\neq w$\u306e\u7b2c1\u6587\u5b57$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064NFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XI.$\\Sigma=\\{a,b,c\\}$, $L=\\{w||w|\\geq 1\\land w $\u306e\u6700\u5f8c3\u6587\u5b57\u306e\u3046\u3061\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f$c$\u3067\u306a\u3044$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064NFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XII.$\\Sigma=\\{a,b,c\\}$, $L=\\{w||w|\\geq 2\\land w $\u306e2\u756a\u76ee\u30684\u756a\u76ee\u306e\u6587\u5b57\u306e\u9593\u3067\u3001\u5c11\u306a\u304f\u3068\u3082 \u4e00\u3064\u6587\u5b57\u306f$c$\u3067\u306a\u3044$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064NFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XIII.$\\Sigma=\\{a,b,c\\}$, $L=\\{w||w|\\geq 4\\land w $\u306e\u6700\u521d\u306e5\u6587\u5b57\u306b\u306f\u90e8\u5206\u6587\u5b57\u5217<strong>$bac$<\/strong>\u304c\u542b\u307e\u308c$\\land$\u6700\u5f8c\u306e5\u6587\u5b57\u306b\u306f\u90e8\u5206\u6587\u5b57\u5217<strong>$acb$<\/strong>\u304c\u542b\u307e\u308c$\\}$\uff0c$L$\u3092\u53d7\u7406\u51fa\u6765\u308b\u4e00\u3064NFA\u3092\u6c42\u3081\u3002\u3053\u306eNFA\u3092DFA\u3078\u8ee2\u63db\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.8 Answer<\/h2>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"2369\" height=\"11661\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8.png\" alt=\"\" class=\"wp-image-444\" style=\"width:840px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8.png 2369w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8-61x300.png 61w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8-208x1024.png 208w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8-768x3780.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8-312x1536.png 312w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/2.8-416x2048.png 416w\" sizes=\"(max-width: 2369px) 100vw, 2369px\" \/><\/figure>\n\n\n\n<p>XIII\u3067\u3001$q_{10}$\u3092\u542b\u3080\u72b6\u614b\u306f\u5168\u3066\u53d7\u7406\u72b6\u614b\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2.9 \u691c\u5b9a\u554f\u984c<\/h2>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\u5927\u83dc\u4e4b\u540e\u4e0a\u3002<\/p>\n<cite>\u3002<\/cite><\/blockquote>\n\n\n\n<h1 class=\"wp-block-heading\">3. \u6b63\u898f\u8868\u73fe<\/h1>\n\n\n\n<blockquote class=\"wp-block-quote has-text-align-right is-layout-flow wp-block-quote-is-layout-flow\">\n<p>DFA\u3001NFA\u3001\u03b5-NFA\u306f\u540c\u3058\u8a00\u8a9e\u8868\u73fe\u80fd\u529b\u3092\u6301\u3064\u2014\u2014\u6b63\u898f\u8a00\u8a9e\u3002<\/p>\n<cite>2.6<\/cite><\/blockquote>\n\n\n\n<p>\u6b63\u898f\u8868\u73fe\u306f\u6b63\u898f\u8a00\u8a9e\u3092\u3088\u308a\u7c21\u6f54\u306b\u8868\u73fe\u3067\u304d\u308b\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.1 \u6982\u5ff5<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>\u8868\u8a18<\/td><td>\u610f\u5473<\/td><\/tr><tr><td>$0$<\/td><td>$\\{0\\}$<\/td><\/tr><tr><td>$0^*$<\/td><td>$\\{\\varepsilon,0,00,000,&#8230;\\}$<\/td><\/tr><tr><td>$0^+$<\/td><td>$\\{0,00,000,&#8230;\\}$<\/td><\/tr><tr><td>$01$<\/td><td>$\\{01\\}$<\/td><\/tr><tr><td>$0+1$<\/td><td>$\\{0,1\\}$<\/td><\/tr><tr><td>$10^+1^*$<\/td><td>$\\{10,101,1011,10111,&#8230;,100,1001,10011,&#8230;,1000,&#8230;\\}$<\/td><\/tr><tr><td>$(0,1)^*$<\/td><td>$\\{\\varepsilon,0,1,00,01,10,11,000,&#8230;\\}$<\/td><\/tr><tr><td>$(1+\\varepsilon)0+1$<\/td><td>$\\{10,0,1\\}$<\/td><\/tr><tr><td>$0\\varnothing$<\/td><td>$\\varnothing$<\/td><\/tr><tr><td>$0+\\varnothing$<\/td><td>$\\{0\\}$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>\u5358\u7d14\u306a\u6b63\u898f\u8868\u73fe\u3092\u66f8\u304f\u306e\u306f\u7c21\u5358\u3067\u3059\u3002\u3088\u308a\u8907\u96d1\u306a\u6b63\u898f\u8868\u73fe\u306f\u901a\u5e38\u3001\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306b\u3088\u3063\u3066\u5909\u63db\u3055\u308c\u307e\u3059\u3002<br>\u8a73\u7d30\u306b\u3064\u3044\u3066\u306f\u3001\u3053\u306e\u90e8\u5206\u306e\u5c0f\u30c6\u30b9\u30c8\u3092\u53c2\u7167\u3057\u3066\u304f\u3060\u3055\u3044\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.2 \u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u304b\u3089\u6b63\u898f\u8868\u73fe\u3078<\/h2>\n\n\n\n<p>\u72b6\u614b\u7e2e\u7d04\u6cd5<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3.2.1 \u539f\u5b50\u7e2e\u7d04<\/h3>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"2406\" height=\"944\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2.png\" alt=\"\" class=\"wp-image-467\" style=\"width:409px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2.png 2406w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2-300x118.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2-1024x402.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2-768x301.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2-1536x603.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.1-2-2048x804.png 2048w\" sizes=\"(max-width: 2406px) 100vw, 2406px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">3.2.2 \u30cd\u30c3\u30c8\u7e2e\u7d04<\/h3>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"2438\" height=\"684\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2.png\" alt=\"\" class=\"wp-image-468\" style=\"width:421px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2.png 2438w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2-300x84.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2-1024x287.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2-768x215.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2-1536x431.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.2.2-2-2048x575.png 2048w\" sizes=\"(max-width: 2438px) 100vw, 2438px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">3.3 \u6b63\u898f\u8868\u73fe\u304b\u3089\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3078<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">3.3.1 \u539f\u5b50\u69cb\u9020<\/h3>\n\n\n\n<p>$a$\u306f\u6b63\u898f\u8868\u73fe\u3002<\/p>\n\n\n\n<div class=\"wp-block-columns\">\n<div class=\"wp-block-column\" style=\"flex-basis:33.33%\">\n<figure class=\"wp-block-table\"><table><tbody><tr><td>$\\varnothing$\u306eFA<\/td><\/tr><tr><td>$\\varepsilon$\u306eFA<\/td><\/tr><tr><td>$a$\u306eFA<\/td><\/tr><\/tbody><\/table><\/figure>\n<\/div>\n\n\n\n<div class=\"wp-block-column\" style=\"flex-basis:66.66%\">\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"574\" height=\"398\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.1-1.png\" alt=\"\" class=\"wp-image-471\" style=\"width:202px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.1-1.png 574w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.1-1-300x208.png 300w\" sizes=\"(max-width: 574px) 100vw, 574px\" \/><\/figure>\n<\/div>\n<\/div>\n\n\n\n<h3 class=\"wp-block-heading\">3.3.2 \u7d50\u5408\u69cb\u9020<\/h3>\n\n\n\n<p>$r$, $s$\u306f\u6b63\u898f\u8868\u73fe\u3002<\/p>\n\n\n\n<div class=\"wp-block-columns\">\n<div class=\"wp-block-column\" style=\"flex-basis:33.33%\">\n<figure class=\"wp-block-table\"><table><tbody><tr><td><br>$r+s$\u306eFA<\/td><\/tr><tr><td><br>$rs$\u306eFA<\/td><\/tr><tr><td><br>$r^*$\u306eFA<\/td><\/tr><\/tbody><\/table><\/figure>\n<\/div>\n\n\n\n<div class=\"wp-block-column\" style=\"flex-basis:66.66%\">\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" width=\"1024\" height=\"710\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.2-1024x710.png\" alt=\"\" class=\"wp-image-470\" style=\"width:319px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.2-1024x710.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.2-300x208.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.2-768x532.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.2.png 1068w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n<\/div>\n\n\n\n<h2 class=\"wp-block-heading\"> 3.4 \u6b63\u898f\u8868\u73fe\u306e\u6027\u8cea<\/h2>\n\n\n\n<p>$R=(RE, +, \\cdot)$\u306f\u534a\u74b0\u3001$RE$\u306f\u6b63\u898f\u8868\u73fe\u306e\u5168\u4f53\u3002<\/p>\n\n\n\n<p>$R$\u306f\u4ee5\u4e0b\u306e\u6027\u8cea\u3092\u6301\u3064\u3002\uff08$L,M,N$\u306f\u6b63\u898f\u8868\u73fe\uff09<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3.4.1 \u4ee3\u6570\u7cfb\u6027\u8cea<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$L+M=M+L$<\/li>\n\n\n\n<li>$(L+M)+N=L+(M+N)$<\/li>\n\n\n\n<li>$(LM)N=L(MN)$<\/li>\n\n\n\n<li>$\\varnothing+L=L+\\varnothing=L$<\/li>\n\n\n\n<li>$\\varepsilon L=L\\varepsilon= L$<\/li>\n\n\n\n<li>$\\varnothing L=L\\varnothing=\\varnothing$<\/li>\n\n\n\n<li>$L(M+N)=LM+LN$<\/li>\n\n\n\n<li>$(M+N)L=ML+NL$<\/li>\n\n\n\n<li>$LM\\neq ML$\uff08\u4e00\u822c\u306f\uff09<\/li>\n\n\n\n<li>$L+L=L$<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">3.4.2 \u4ed6\u306e\u6027\u8cea<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$(L^*)^*=L^*$<\/li>\n\n\n\n<li>$\\varnothing^*=\\varepsilon$<\/li>\n\n\n\n<li>$\\varepsilon^*=\\varepsilon$<\/li>\n\n\n\n<li>$L^*=L^++\\varepsilon$<\/li>\n\n\n\n<li>$L^+=LL^*=L^*L$<\/li>\n\n\n\n<li>$L=\\varepsilon+L$<\/li>\n\n\n\n<li>$(L+M)^*=(L^*M^*)^*$<\/li>\n\n\n\n<li>$L^*L^*=L^*$<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">3.4.3 \u69cb\u9020\u7684\u6027\u8cea<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">3.4.3.1 <strong>\u53cd\u8907\u88dc\u984c<\/strong><\/h4>\n\n\n\n<p>\u6b63\u898f\u8a00\u8a9e$R$\u306b\u5bfe\u3057\u3066\u6b21\u306e\u6761\u4ef6\u3092\u6e80\u305f\u3059\u5b9a\u6570$N$\u304c\u5b58\u5728\u3059\u308b\u3002<br>$|w|\\geq N$\u306e$R$\u5185\u306e\u8a9e$w$\u306f\u6b21\u306e\u6761\u4ef6\u3092\u6e80\u305f\u3059\u3088\u3046\u306b$w = xyz$\u3068\u5206\u89e3\u3067\u304d\u308b\u3002<\/p>\n\n\n\n<p>(1) $|xy| \\leq N$<br>(2) $|y| \\geq 1$\u307e\u305f\u306f$y\\neq\\varepsilon$<br>(3) $\\forall i \\geq 0(xy^iz\\in R)$<\/p>\n\n\n\n<p>\u3053\u306e\u5b9a\u6570$N$\u306f\u3001$R$\u3092\u53d7\u7406\u3059\u308b\u6700\u5c0f(\u72b6\u614b\u6570\u304c\u6700\u3082\u5c11\u306a\u3044)\u306e\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306e\u72b6\u614b\u6570\u3092\u8d8a\u3048\u306a\u3044\u3002<br>\u7279\u306b\u3001\u6709\u9650\u8a00\u8a9e\u306e\u5834\u5408\u3001\u53cd\u8907\u88dc\u984c\u3082\u6210\u7acb\u3002<\/p>\n\n\n\n<p><br>\u3053\u306e\u88dc\u984c\u306f\u3001\u6b63\u898f\u8a00\u8a9e\u3067\u306f\u306a\u3044\u3068\u5224\u65ad\u3059\u308b\u3057\u304b\u306a\u3044\u3002<br>\u3064\u307e\u308a\u3001\u53cd\u8907\u88dc\u984c\u306e\u6210\u7acb\u306f\u8a00\u8a9e\u6b63\u898f\u6027\u306e\u6210\u7acb\u3092\u4fdd\u8a3c\u3059\u308b\u3082\u306e\u3067\u306f\u306a\u3044\u3002<br><\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>Myhill-Nerode\u5247<\/p>\n<cite>$\\Sigma$\u4e0a\u306e\u8a00\u8a9e $L$\u306b\u5bfe\u3057\u3066\u5b9a\u7fa9\u3055\u308c\u308b\u53f3\u4e0d\u5909\u306a\u540c\u5024\u95a2\u4fc2\u3092$R_L$\u3068\u3059\u308b\u3068\u304d\u3001\u4ee5\u4e0b\u306e\u547d\u984c\u306f\u4e92\u3044\u306b\u540c\u7b49\u3067\u3042\u308b\u3002\u3053\u3053\u3067\u3001\u540c\u5024\u95a2\u4fc2\u306e\u6307\u6570\u3068\u306f\u305d\u306e\u540c\u5024\u985e\u306e\u6fc3\u5ea6 (\u96c6\u5408\u306e\u8981\u7d20\u6570)\u3067\u3042\u308b\u3002<br>(1)$L$\u306f\u6b63\u898f\u8a00\u8a9e(\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306e\u53d7\u7406\u96c6\u5408)\u3067\u3042\u308b\u3002<br>(2)$L$\u306f\u3001\u6709\u9650\u6307\u6570\u3092\u6301\u3064\u53f3\u4e0d\u5909\u306a\u540c\u5024\u95a2\u4fc2$R_i$\u306e\u305d\u306e\u5e7e\u3064\u304b\u306e\u540c\u5024\u985e\u306e\u76f4\u548c\u3068\u3057\u3066\u8868\u3055\u308c\u308b\u3002<br>(3)\u540c\u5024\u95a2\u4fc2 $R_L$\u306e\u6307\u6570\u306f\u6709\u9650\u3067\u3042\u308b\u3002<\/cite><\/blockquote>\n\n\n\n<h4 class=\"wp-block-heading\">3.4.3.2 \u6b63\u898f\u8868\u73fe\u306e\u7d50\u5408<\/h4>\n\n\n\n<p>$L,R$\u306f\u6b63\u898f\u8868\u73fe\u3002\u306a\u3089\u6b21\u306e\u5f62\u5f0f\u3082\u6b63\u898f\u8868\u73fe\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$LR$<\/li>\n\n\n\n<li>$L\\cup R$<\/li>\n\n\n\n<li>$L^*$<\/li>\n\n\n\n<li>$\\bar L$<\/li>\n\n\n\n<li>$L\\cap R$<\/li>\n\n\n\n<li>$\\varphi(L)$, $\\varphi:\\Sigma\\rightarrow\\Gamma^*$\u306f2\u3064\u306e\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\uff08\u6e96\u540c\u578b\uff09\u5199\u50cf<\/li>\n\n\n\n<li>$\\varphi^{-1}(R)$, $\\varphi:\\Sigma\\rightarrow\\Gamma^*$\u306f2\u3064\u306e\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\uff08\u9006\u6e96\u540c\u578b\uff09\u5199\u50cf<\/li>\n\n\n\n<li>$L^R$\u3001\u3053\u3053\u306e$R$\u306f\u30ea\u30d0\u30fc\u30b9<\/li>\n\n\n\n<li>$L-R$<\/li>\n<\/ul>\n\n\n\n<p>DFA\u306e\u69cb\u9020\u65b9\u6cd5<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" width=\"1024\" height=\"339\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.4.2.1-1024x339.png\" alt=\"\" class=\"wp-image-509\" style=\"width:374px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.4.2.1-1024x339.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.4.2.1-300x99.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.4.2.1-768x254.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/3.3.4.2.1.png 1246w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u3002\u3002\u3002\u3002\u3002\u3002\u3002\u3002\u8fd8\u6ca1\u51c6\u5907\u597d\u56fe\u3002\u3002\u3002\u3002\u3002\u3002\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.5 \u6b63\u898f\u8a00\u8a9e\u306e\u5224\u5b9a\u554f\u984c<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">3.5.1 \u6b63\u898f\u8868\u73fe\u306e\u7a7a\u6027\u3001\u6709\u9650\u6027<\/h3>\n\n\n\n<p>$n$\u3064\u72b6\u614b\u3092\u6301\u3064\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3$M$\u306e\u8a00\u8a9e\u304c\u7a7a$\\leftrightarrow$ $\\forall w(w\\in \\Sigma^* \\land |w|\\leq n\\rightarrow w\\notin L(M))$<br>$n$\u3064\u72b6\u614b\u3092\u6301\u3064\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3$M$\u306e\u8a00\u8a9e\u304c\u7121\u9650\u96c6\u5408$\\leftrightarrow$ $\\exists w(w\\in \\Sigma^* \\land n\\leq |w|\\leq 2n\\rightarrow w\\in L(M))$<br><\/p>\n\n\n\n<p>\u3057\u305f\u304c\u3063\u3066\u3001\u6b63\u898f\u8868\u73fe\u306b\u5bfe\u3057\u3066:<br> \u53d7\u7406\u96c6\u5408\u304c\u7a7a\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5b58\u5728\u3057\u3001\u305d\u308c\u306f\u9577\u3055\u304c$n$\u672a\u6e80\u306e\u5168\u3066\u306e\u6587\u5b57\u5217\u3092\u30c1\u30a7\u30c3\u30af\u3059\u308b\u3067\u3088\u3044\u3002<br> \u53d7\u7406\u96c6\u5408\u304c\u7121\u9650\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5b58\u5728\u3057\u3001\u305d\u308c\u306f\u9577\u3055\u304c$n$\u304b\u3089$2n\u22121$\u307e\u3067\u306e\u5168\u3066\u306e\u6587\u5b57\u5217\u3092\u30c1\u30a7\u30c3\u30af\u3059\u308b\u3067\u3088\u3044\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">3.5.2 \u6b63\u898f\u8868\u73fe\u306e\u540c\u5024\u6027<\/h3>\n\n\n\n<p>\u6709\u9650\u30aa\u30fc\u30c8\u30de\u30c8\u30f3$M,N$\u306b\u540c\u5024\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5b58\u5728\u3057\u3002<br>$(\\bar L(M)\\cap L(N))\\cup(L(M)\\cap \\bar L(N))$\u306e\u7a7a\u6027\u3092\u5224\u65ad\u3059\u308b\u3067\u3088\u3044\u3002<\/p>\n\n\n\n<p><br>\u5f93\u3063\u3066\u3001\u6b63\u898f\u8868\u73fe\u306e\u540c\u5024\u6027\u3092\u5224\u65ad\u3059\u308b\u65b9\u6cd5\u3082\u3042\u308b\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.6 DFA\u306e\u6700\u5c0f\u5316<\/h2>\n\n\n\n<p>\u540c\u5024\u72b6\u614b\uff1a<\/p>\n\n\n\n<p>(1)\u53d7\u7406\u72b6\u614b<br>(2)<br>(3)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.7 \u5c0f\u30c6\u30b9\u30c8<\/h2>\n\n\n\n<p>I.$(a+b)^*(a+bb)$\u306f\u4f55\u3002<\/p>\n\n\n\n<p>II.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|= 2\\land w $\u306e\u7b2c2\u6587\u5b57\u306f$1\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>III.$\\Sigma=\\{0,1\\}$, $L=\\{w|000$\u306f$w$\u306e\u90e8\u5206\u6587\u5b57\u5217$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.$\\Sigma=\\{0,1\\}$, $L=\\{w$\u306e\u6700\u5f8c2\u6587\u5b57\u306f$01\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>V.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u306e\u6700\u521d\u6587\u5b57$=$\u306e\u6700\u5f8c\u6587\u5b57$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VI.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067$0$\u306e\u5f8c\u306b$1$, $1$\u306e\u5f8c\u306b$0\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VII.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u3067$0$\u306e\u5f8c\u306b$1$, $1$\u306e\u5f8c\u306b$0\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VIII.$\\Sigma=\\{0,1\\}$, $L=\\{w$\u306e\u5f8c\u308d\u304b\u30895\u756a\u76ee\u6587\u5b57\u304c$1\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IX.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|\\geq 1\\land w $\u306e\u6700\u521d5\u6587\u5b57\u306e\u3046\u3061\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f$1\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>X.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|\\geq 1\\land w $\u306e\u6700\u5f8c5\u6587\u5b57\u306e\u3046\u3061\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f$1\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XI.$\\Sigma=\\{a,b,c\\}$, $L=\\{w|a,b$\u306f$w$\u306e\u6587\u5b57$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XII.$\\Sigma=\\{0,1\\}$, $L=\\{w|$\u5168\u3066\u306e$00$\u306f$11$\u306e\u524d\u3067\u51fa\u73fe$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XIII.$\\Sigma=\\{0,1\\}$, $L=\\{w=xy|x\\in\\Sigma^*\\land y=y^R\\land |y|=3$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XIV.$\\Sigma=\\{0,1\\}$, $L=\\{w|00,11$\u306f$w$\u306e\u90e8\u5206\u6587\u5b57\u5217\u3067\u306f\u306a\u3044$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XV.$\\Sigma=\\{0,1\\}$, $L=\\{w=0^m1^n|m,n\\geq 0\\land 2\\mid(m+n)$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XVI.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u306e\u6700\u5f8c\u6587\u5b57\u306f$1$\u306a\u3089$2\\nmid|w|\\land |w|\\geq 1$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XVII.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|\\geq 2\\land w $\u306e\u6700\u521d\u306e5\u6587\u5b57\u306b\u306f\u90e8\u5206\u6587\u5b57\u5217$00$\u304c\u542b\u307e\u308c\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XVIII.$\\Sigma=\\{0,1\\}$, $L=\\{w||w|\\geq 2\\land w $\u306e2\u756a\u76ee\u30685\u756a\u76ee\u306e\u6587\u5b57\u306e\u9593\u3067\u3001\u5c11\u306a\u304f\u3068\u3082\u4e00\u3064\u6587\u5b57\u306f$1\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XIX.$\\Sigma=\\{0,1\\}$, $L=\\{w|w$\u306e\u5f8c\u308d\u304b\u30895\u756a\u76ee\u6587\u5b57\u304c$1,w$\u306b\u306f\u3001$1$\u304c3\u3064\u3060\u3051\u3042\u308a\u307e\u3059$\\}$\uff0c$L$\u306e\u4e00\u3064\u6b63\u898f\u8868\u73fe\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XX.$(0+1)^*1(0+1)$\u306eNFA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XXI.$L=\\{0^n1^n\\}$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XXII.$L=\\{w$\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\}$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XXIII.$L=\\{0^i1^j|i&gt;j\\}$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XXIV.$L=\\{0^{n!}\\}$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XXV.$L=\\{0^n(0+1)^*1^n)\\}$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u3059\u304b\u3002<\/p>\n\n\n\n<p>XXVI.$\\Sigma=\\{0,1\\}$, $L=\\{w|w=w^R\\}$\uff0c$L$\u306f\u6b63\u898f\u8a00\u8a9e\u3067\u3059\u304b\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3.8 Answer<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\">3.9 \u691c\u5b9a\u554f\u984c<\/h2>\n\n\n\n<h1 class=\"wp-block-heading\">4. \u6587\u8108\u81ea\u7531\u6587\u6cd5<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">4.1 \u6982\u5ff5<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.1.1 \u6587\u8108\u81ea\u7531\u6587\u6cd5<\/h3>\n\n\n\n<p>$G=(V,T,P,S)$<\/p>\n\n\n\n<p>$V$\u306f\u975e\u7d42\u7aef\u8a18\u53f7\u96c6\u5408\u3001$T$\u306f\u7d42\u7aef\u8a18\u53f7\u96c6\u5408\u3001$P$\u306f\u751f\u6210\u898f\u5247\u96c6\u5408\u3001$S\\in V$\u306f\u958b\u59cb\u8a18\u53f7\u3002<br>$P$\u306e\u5143\u306f\u751f\u6210\u898f\u5247\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.1.2 \u6587\u8108\u81ea\u7531\u8a00\u8a9e<\/h3>\n\n\n\n<p>$T^*$\u4e0a\u306e\u8a00\u8a9e$L\\subseteq T^\u2217$ \u306b\u5bfe\u3057\u3066\u3001$L$\u3092\u751f\u6210\u3059\u308b\u6587\u8108\u81ea\u7531\u6587\u6cd5$G$\u304c\u5b58\u5728\u3059\u308b\u3068\u304d\u3001$L$\u3092\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<p>$L=\\{w|w\\in T^*\\land S\\Rightarrow w\\}$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.1.3 \u5c0e\u51fa\u3068\u5e30\u7d50<\/h3>\n\n\n\n<p>\u3042\u308b\u751f\u6210\u898f\u5247$A\\rightarrow \\gamma$\u306b\u3088\u3063\u3066\u3001<br>$\\alpha A\\beta\\Rightarrow\\alpha\\gamma\\beta$\u3068\u3044\u3046\u64cd\u4f5c\u3092\u5c0e\u51fa\u3068\u3044\u3044\u3001<br>$\\alpha A\\beta\\Leftarrow\\alpha\\gamma\\beta$\u3068\u3044\u3046\u64cd\u4f5c\u3092\u5e30\u7d50\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.1.4 \u6700\u5de6\u5c0e\u51fa\u3068\u6700\u53f3\u5c0e\u51fa<\/h3>\n\n\n\n<p>\u6700\u5de6\u5c0e\u51fa\uff1a\u6587\u5b57\u5217\u306e\u6700\u5de6\u975e\u7d42\u7aef\u8a18\u53f7\u306e\u307f\u3092\u7f6e\u304d\u63db\u3048\u308b\u5c0e\u51fa\u3002<br>\u6700\u53f3\u5c0e\u51fa\uff1a\u6587\u5b57\u5217\u306e\u6700\u53f3\u975e\u7d42\u7aef\u8a18\u53f7\u306e\u307f\u3092\u7f6e\u304d\u63db\u3048\u308b\u5c0e\u51fa\u3002<br>\u6700\u5de6\u5c0e\u51fa\u3001\u6700\u53f3\u5c0e\u51fa\u306f\u4e00\u610f\u5b58\u5728\u7684\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.1.5 \u69cb\u6587\u6728<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">\u3002\u3002\u3002\u3002\u3002<br><\/h4>\n\n\n\n<h2 class=\"wp-block-heading\">4.2 \u66d6\u6627\u6587\u6cd5<\/h2>\n\n\n\n<p>\u6587\u8108\u81ea\u7531\u6587\u6cd5$G$\u3067\u3001\u3042\u308b\u8a9e$w \u2208 L(G)$\u306b\u5bfe\u3057\u3066 2 \u3064\u4ee5\u4e0a\u5c0e\u51fa\u6728\u3092\u6301\u3064\u6642\u3001$G$\u306f\u66d6\u6627\u6587\u6cd5\u3068\u3044\u3044\u3002<br>\u4e00\u90e8\u306e\u66d6\u6627\u6587\u6cd5\u306f\u3001\u6587\u6cd5\u518d\u69cb\u7bc9\u306b\u3088\u3063\u3066\u66d6\u6627\u3055\u3092\u56de\u907f\u3067\u304d\u308b\u3002\u3067\u3059\u304c\u3001\u6587\u6cd5\u518d\u69cb\u7bc9\u3067\u3082\u66d6\u6627\u3055\u3092\u56de\u907f\u3067\u304d\u306a\u3044\u72b6\u6cc1\u3082\u3042\u308b\u3002\u3053\u306e\u6642\u306f\u3001\u3053\u306e\u6587\u8108\u81ea\u7531\u6587\u6cd5\u306f\u672c\u8cea\u66d6\u6627\u7684\u3068\u3044\u3044\u3001\u305d\u306e\u8a00\u8a9e\u3092\u672c\u8cea\u66d6\u6627\u8a00\u8a9e\u3068\u3044\u3044\u3002<br>$L=\\{a^ib^jc^k|i=j\\lor j=k\\}$\u306f\u672c\u8cea\u66d6\u6627\u8a00\u8a9e\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.3 \u6587\u6cd5\u6a19\u6e96\u5316<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.3.1 <strong>\u6587\u6cd5\u7c21\u7d04\u5316<\/strong><\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">4.3.1.1 \u7121\u7528\u8a18\u53f7\u306e\u9664\u53bb<\/h4>\n\n\n\n<p>\u751f\u8a18\u53f7\u96c6\u5408<br>$G_s=T\\cup\\{X|X\\Rightarrow w\\land w\\in \\Sigma^*\\land X\\in V\\}$<br>\u5230\u9054\u53ef\u80fd\u8a18\u53f7<br>$R_s=\\{S\\}\\cup\\{X|X$\u306f$\\alpha$\u306e\u6587\u5b57$\\land Y\\rightarrow \\alpha\\in P \\land Y\\in R_s\\}$<br>\u7121\u7528\u8a18\u53f7\u306f<br>$U_s=V\\cup T-G_s-R_s$<br>$P$\u3067\u3001$U_s$\u306e\u5143\u3092\u542b\u3080\u751f\u6210\u898f\u5247\u3092$P$\u304b\u3089\u9664\u53bb\u3002<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">4.3.1.2 \u03b5-\u751f\u6210\u898f\u5247\u306e\u9664\u53bb<\/h4>\n\n\n\n<p>\u3002\u3002\u3002\u3002\u3002\u3002<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">4.3.1.3 \u5358\u4f4d\u898f\u5247\u306e\u9664\u53bb<\/h4>\n\n\n\n<p>$A\\rightarrow B, B\\rightarrow w$\u306a\u3089$A\\rightarrow w$\u3092\u7528\u3044\u3066\u7c21\u7d04<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.3.2 \u6587\u6cd5\u6a19\u6e96\u5f62<\/h3>\n\n\n\n<h4 class=\"wp-block-heading\">4.3.2.1 \u30c1\u30e7\u30e0\u30b9\u30ad\u30fc\u6a19\u6e96\u5f62<\/h4>\n\n\n\n<p>$\\varepsilon$\u306a\u3057\u6587\u8108\u81ea\u7531\u6587\u6cd5\u306e\u751f\u6210\u898f\u5247\u306f\u5168\u3066\u6b21\u306e\u3088\u3046\u306a\u5f62\u5f0f\u3078\u5909\u63db\u3067\u304d\u308b\u3002<br>$A\\rightarrow BC, A\\rightarrow a(A,B,C\\in V, a\\in T)$<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">4.3.2.2 \u30b0\u30e9\u30a4\u30d0\u30c3\u30cf\u6a19\u6e96\u5f62<\/h4>\n\n\n\n<p>\u6587\u8108\u81ea\u7531\u6587\u6cd5\u306e\u751f\u6210\u898f\u5247\u306f\u5168\u3066\u6b21\u306e\u3088\u3046\u306a\u5f62\u5f0f\u3078\u5909\u63db\u3067\u304d\u308b\u3002<br>$A\\rightarrow a\\alpha(A\\in V, a\\in T, \\alpha\\in V^*)$<\/p>\n\n\n\n<p>\u7279\u306b$A\\rightarrow A\\alpha|\\beta$\u306f\u6b21\u306e2\u5f0f\u3078\u5909\u63db\u3002<br>$A\\rightarrow \\beta B|\\beta$<br>$B\\rightarrow \\alpha B|\\alpha$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.4 \u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.4.1 \u57fa\u672c\u6982\u5ff5<\/h3>\n\n\n\n<p>$PDA=(Q,\\Sigma,\\Gamma,\\delta,q_0,Z_0,F)$<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$Q$\u306f\u72b6\u614b\u96c6\u5408\u3001$\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\Gamma$\u306f\u30b9\u30bf\u30c3\u30af\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\delta$\u306f\u72b6\u614b\u9077\u79fb\u95a2\u6570\u3001$q_0$\u306f\u521d\u671f\u72b6\u614b\u3001$Z_0$\u30b9\u30bf\u30c3\u30af\u672b\u7aef\u8a18\u53f7\u3001$F$\u306f\u53d7\u7406\u72b6\u614b\u96c6\u5408\u3002<\/p>\n\n\n\n<p>$\\delta: Q\\times(\\Sigma\\cup\\{\\varepsilon\\})\\times\\Gamma\\rightarrow 2^{Q\\times\\Gamma^*}$\u3002<\/p>\n\n\n\n<p>\u72b6\u614b\u9077\u79fb\u8868\u8a18$p,X\/\\alpha$\u306f\u3001<br>$p$\u3092\u5165\u529b\u306e\u3068\u304d\u3001\u4eca\u306e\u30b9\u30bf\u30c3\u30af\u9802\u7aef\u8a18\u53f7\u306f$X$\u3001\u3053\u306e$X$\u3092\u30dd\u30c3\u30d7\u30a2\u30a6\u30c8\u3001$\\alpha$\u306e\u6587\u5b57\u3092\u4e00\u3064\u305a\u3064\u30b9\u30bf\u30c3\u30af\u3078\u30d7\u30c3\u30b7\u30e5\u3002<\/p>\n\n\n\n<p>\u5373\u5ea7\u89e3\u91c8<br>(\u4eca\u306e\u72b6\u614b\u3001\u307e\u3060\u53d7\u3051\u3089\u308c\u306a\u3044\u6587\u5b57\u5217\u3001\u30b9\u30bf\u30c3\u30af\u72b6\u6cc1)<br>\u5373\u5ea7\u89e3\u91c8\u306e\u72b6\u614b\u9077\u79fb<br>\u4f8b\uff1a$\\{q_3,abbac,XZYZ_0\\} \\vdash\\{q_4,bbac,YYZYZ_0\\}$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.4.2 \u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306e\u53d7\u7406\u8a00\u8a9e<\/h3>\n\n\n\n<p>$L(P) = \\{w|(q_0,w,Z_0)\\vdash^*(p,\\varepsilon,\\alpha)\\land p\\in F\\}$\u306f$P$\u306e\u72b6\u614b\u53d7\u7406\u8a00\u8a9e\u3068\u3044\u3044\u3002<br>$N(P) = \\{w|(q_0,w,Z_0)\\vdash^*(p,\\varepsilon,\\varepsilon)\\}$\u306f$P$\u306e\u30b9\u30bf\u30c3\u30af\u53d7\u7406\u8a00\u8a9e\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<p>$P_N$\uff08\u30b9\u30bf\u30c3\u30af\u53d7\u7406\uff09$\\Leftrightarrow P_F$\uff08\u72b6\u614b\u53d7\u7406\uff09\u306e\u65b9\u6cd5<\/p>\n\n\n\n<p>$P_F\\rightarrow P_N$<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"2872\" height=\"772\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1.png\" alt=\"\" class=\"wp-image-593\" style=\"width:602px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1.png 2872w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1-300x81.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1-1024x275.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1-768x206.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1-1536x413.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.1-2048x551.png 2048w\" sizes=\"(max-width: 2872px) 100vw, 2872px\" \/><\/figure>\n\n\n\n<p>$P_N\\rightarrow P_F$<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img decoding=\"async\" width=\"2458\" height=\"984\" src=\"https:\/\/www.yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2.png\" alt=\"\" class=\"wp-image-594\" style=\"width:596px;height:auto\" srcset=\"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2.png 2458w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2-300x120.png 300w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2-1024x410.png 1024w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2-768x307.png 768w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2-1536x615.png 1536w, https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/06\/4.4.2.2-2048x820.png 2048w\" sizes=\"(max-width: 2458px) 100vw, 2458px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">4.4.3 CFG\u304b\u3089PDA\u3078<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>PDA\u306e\u69cb\u9020\u306f\u30b9\u30bf\u30c3\u30af\u53d7\u7406\u7684$start\\rightarrow\\LARGE\\circ\\small q_0$<\/li>\n\n\n\n<li>\u5168\u3066\u306e\u751f\u6210\u898f\u5247$A\\rightarrow \\alpha$\u306b\u3001$q_0$\u3067\u72b6\u614b\u9077\u79fb\u898f\u5247$\\varepsilon,A\/\\alpha$\u3092\u3064\u3051\u3066<\/li>\n\n\n\n<li>\u5168\u3066\u306e\u7d42\u7aef\u8a18\u53f7$t\\in T$\u306b\u3001$q_0$\u3067\u72b6\u614b\u9077\u79fb\u898f\u5247$t,t\/\\varepsilon$\u3092\u3064\u3051\u3066<\/li>\n<\/ul>\n\n\n\n<p>\u7279\u306b\u3001\u3082\u3057CFG\u306f\u30b0\u30e9\u30a4\u30d0\u30c3\u30cf\u6a19\u6e96\u5f62\u3001\u306a\u3089\u5168\u3066\u306e\u751f\u6210\u898f\u5247$A\\rightarrow a\\alpha$\u306b\u3001$q_0$\u3067\u72b6\u614b\u9077\u79fb\u898f\u5247$a,A\/\\alpha$\u3092\u3064\u3051\u3066\u3067\u3044\u3044\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.4.4 PDA\u304b\u3089CFG\u3078<\/h3>\n\n\n\n<p>$P=(Q,\\Sigma,\\Gamma,\\delta,q_0,Z_0,F)$\u306e\u6587\u8108\u81ea\u7531\u6587\u6cd5$G=(V,T,P,S)$\u3092\u6c42\u3081<\/p>\n\n\n\n<p>\u751f\u6210\u898f\u5247\u96c6\u5408$P$\u3067\u3001<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>(1) $\\forall p\\in Q$\u306b\u5bfe\u3057\u3066\u3001$|Q|$\u3064\u306e\u751f\u6210\u898f\u5247$S\\rightarrow [q_0Z_0p]$\u3092\u6dfb\u4ed8\u3002 <\/li>\n\n\n\n<li>(2) $\\forall (p,Y_1Y_2\\cdots Y_n)\\in \\delta(q,a,X)$\u306b\u5bfe\u3057\u3066\u3001$|Q|^n$\u3064\u306e\u751f\u6210\u898f\u5247$[qXr_n]\\rightarrow a[pY_1r_1][r_1Y_2r_2] \u00b7 \u00b7 \u00b7 [\ud835\udc5f_{\ud835\udc5b\u22121}Y_nr_n]$\u3092\u6dfb\u4ed8\u3002 <br>$a\\in\\Sigma\\cup\\{\\varepsilon\\}, X,Y_i\\in\\Gamma, r_i$\u306f$Q$\u5185\u306e\u4efb\u610f\u72b6\u614b\u3002<br>$Y_1Y_2\\cdots Y_n=\\varepsilon$\u3068\u3059\u308b\u3068\u3001\u751f\u6210\u898f\u5247\u306f$[qXp]\\rightarrow a$\u3002<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">4.5 \u6c7a\u5b9a\u7684\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.5.1 \u57fa\u672c\u6982\u5ff5<\/h3>\n\n\n\n<p>$PDA=(Q,\\Sigma,\\Gamma,\\delta,q_0,Z_0,F)$\u306b\u3001\u6b21\u306e2\u6761\u4ef6\u3092\u6e80\u8db3\u306a\u3089\u3053\u308c\u3092\u6c7a\u5b9a\u7684\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<p>$\\forall a(a\\in\\Sigma\\cup\\{\\varepsilon\\} \\rightarrow |\\delta(p,a,X)|\\leq1)$<br>$\\forall a(a\\in\\Sigma\\land|\\delta(p,a,X)|=1\\rightarrow\\delta(p,\\varepsilon,X)=\\varnothing)$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.5.2 PDA\u3068\u306e\u533a\u5225<\/h3>\n\n\n\n<p>DPDA\u306f$\\{ww^R\\}$\u3092\u53d7\u7406\u51fa\u6765\u306a\u3044\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.5.3 DPDA\u306e\u53d7\u7406\u8a00\u8a9e<\/h3>\n\n\n\n<p>\u8a9e\u982d\u5c5e\u6027\u3092\u6e80\u305f\u3059\u3068\u306f\u3001\u4efb\u610f\u306e\u8a9e\u304c\u4ed6\u306e\u3044\u304b\u306a\u308b\u8a9e\u306e\u63a5\u982d\u90e8\u306b\u306a\u3063\u3066\u3044\u306a\u3044\u3068\u3044\u3046\u5c5e\u6027\u3067\u3042\u308b\u3002<\/p>\n\n\n\n<p>\u3042\u308bDPDA\u306e\u30b9\u30bf\u30c3\u30af\u53d7\u7406\u8a00\u8a9e\u306f$L \\Leftrightarrow L$\u306f\u8a9e\u982d\u5c5e\u6027\u3092\u6e80\u305f\u3059\u3002<\/p>\n\n\n\n<p>DPDA\u306e\u72b6\u614b\u53d7\u7406\u8a00\u8a9e\u306f\u6c7a\u5b9a\u7684\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<p>DPDA\u306e\u53d7\u7406\u8a00\u8a9e\u306e\u6587\u6cd5\u306f\u672c\u8cea\u66d6\u6627\u6587\u6cd5\u3067\u306f\u306a\u3044\u3002<br>\u672c\u8cea\u66d6\u6627\u3067\u306a\u3044\u8a00\u8a9e\u306fDPDA\u306b\u3088\u3063\u3066\u8b58\u5225\u3068\u9650\u3089\u306a\u3044\u3002<\/p>\n\n\n\n<p>\u30b9\u30bf\u30c3\u30af\u53d7\u7406$DPDA\\subset$\u72b6\u614b\u53d7\u7406$DPDA\\subset PDA\\subset LBA\\subset TM$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.6 \u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u69cb\u9020\u7684\u6027\u8cea<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.6.1 <strong>\u53cd\u8907\u88dc\u984c<\/strong><\/h3>\n\n\n\n<p>\u6587\u8108\u81ea\u7531\u8a00\u8a9e$L$\u306b\u5bfe\u3057\u3066\u6b21\u306e\u6761\u4ef6\u3092\u6e80\u305f\u3059\u5b9a\u6570$N$\u304c\u5b58\u5728\u3059\u308b\u3002<br>$|z|\\geq N$\u306e$L$\u5185\u306e\u8a9e$z$\u306f\u6b21\u306e\u6761\u4ef6\u3092\u6e80\u305f\u3059\u3088\u3046\u306b$z = uvwxy$\u3068\u5206\u89e3\u3067\u304d\u308b\u3002<\/p>\n\n\n\n<p>(1) $|vwx| \\leq N$,<br>(2) $|vx| \\geq 1$\u307e\u305f\u306f$vx\\neq\\varepsilon$,<br>(3) $\\forall i \\geq 0 (uv^iwx^iy\\in L)$.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.6.2 \u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u7d50\u5408<\/h3>\n\n\n\n<p>$L,R$\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3002<br>\u5176\u3005\u306e\u6587\u6cd5\u306f$G_L=\\{V_L,T_L,P_L,S_L\\}$,$G_R=\\{V_R,T_R,P_R,S_R\\}$<br>\u306a\u3089\u6b21\u306e\u5f62\u5f0f\u3082\u6587\u8108\u81ea\u7531\u8a00\u8a9e\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$LR$<br>$G_{LR}=\\{V_L\\cup V_R\\cup\\{S\\}, T_L\\cup T_R, P_L\\cup P_R\\cup\\{S\\rightarrow S_LS_R\\}, S\\}$<\/li>\n\n\n\n<li>$L\\cup R$<br>$G_{L\\cup R}=\\{V_L\\cup V_R\\cup\\{S\\}, T_L\\cup T_R, P_L\\cup P_R\\cup\\{S\\rightarrow S_L|S_R\\}, S\\}$<\/li>\n\n\n\n<li>$L^*$<br>$G_{L^*}=\\{V_L\\cup\\{S\\}, T_L, P_L\\cup\\{S\\rightarrow S_LS|\\epsilon\\}, S\\}$<\/li>\n\n\n\n<li>$\\varphi(L)$, $\\varphi:\\Sigma\\rightarrow\\Gamma^*$\u306f2\u3064\u306e\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\uff08\u6e96\u540c\u578b\uff09\u5199\u50cf<\/li>\n\n\n\n<li>$\\varphi^{-1}(R)$, $\\varphi:\\Sigma\\rightarrow\\Gamma^*$\u306f2\u3064\u306e\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u306e\uff08\u9006\u6e96\u540c\u578b\uff09\u5199\u50cf<\/li>\n\n\n\n<li>$L^R$\u3001\u3053\u3053\u306e$R$\u306f\u30ea\u30d0\u30fc\u30b9<br>$G_{L^R}=\\{V_L,T_L,\\{A\\rightarrow\\alpha^R|A\\rightarrow\\alpha\\in P_L\\},S_L\\}$<\/li>\n\n\n\n<li>$\\tau(L)$, $\\tau : \\Sigma\\rightarrow2^{\\Gamma^*}$\u306f\u4ee3\u63db\u3068\u3044\u3044\u3002<br>\u4ee3\u63db\u306f\u300c$\\Sigma$\u306e\u6587\u5b57\u3092$\\Gamma$\u3067\u306e\u3042\u308b\u8a00\u8a9e\u3078\u5199\u50cf\u300d\u3002<\/li>\n<\/ul>\n\n\n\n<p>\u6b21\u306e\u5f62\u5f0f\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3067\u306a\u3044\u3082\u53ef\u80fd\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>$L\\cap R$<\/li>\n\n\n\n<li>$\\bar L$<\/li>\n<\/ul>\n\n\n\n<p>\u305f\u3060\u3057\u3001\u3082\u3057$R$\u306f\u6b63\u898f\u8a00\u8a9e\u3001\u306a\u3089$L\\cap R$\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3002<br>\u3053\u3053\u306f\u30011\u3064\u306e\u72b6\u614b\u53d7\u7406PDA\u306fL\u3092\u5b9f\u73fe\u3001DFA\u306fR\u3092\u5b9f\u73fe\u30022\u3064\u306e\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u304c\u540c\u6642\u53d7\u7406\u3067\u3044\u3044\u3002<br>$PDA_{L}=(Q_P,\\Sigma,\\Gamma,\\delta_P,q_P,Z_0,F_P)$<br>$DFA_{R}=(Q_D,\\Sigma,\\delta_D,q_D,F_D)$<br>$PDA_{L\\cap R}=(Q_P\\times Q_D, \\Sigma,\\Gamma,\\delta,[q_p,q_d],Z_0,F_P\\times F_D)$<br>$\\delta([p,q],\\varepsilon,X)=\\{([p,s],\\beta)|(s,\\beta)\\in\\delta_P(q,\\varepsilon,X)\\}$<br>$\\delta([p,q],a,X)=\\{([r,s],\\beta)|r=\\delta_D(p,a)\\land(s,\\beta)\\in\\delta_P(q,a,X)\\}(a\\in\\Sigma)$<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.6 \u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u5224\u5b9a\u554f\u984c<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">4.6.1 \u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u5224\u5b9a\u53ef\u80fd\u554f\u984c<\/h3>\n\n\n\n<p>$S$\u304c\u751f\u8a18\u53f7\u306a\u3089\u3053\u306e\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306f\u7a7a\u3058\u3083\u306a\u3044\u3002<br>CYK\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3042\u308b\u8a9e$w$\u304c$L(G)$\u5185\u306b\u3042\u308b\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3001\u7279\u306b$G$\u306f\u65e2\u306b\u30c1\u30e7\u30e0\u30b9\u30ad\u30fc\u6a19\u6e96\u5f62\u5316\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">4.6.2 \u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u5224\u5b9a\u4e0d\u53ef\u80fd\u554f\u984c<\/h3>\n\n\n\n<p>\u6b21\u306e\u3082\u306e\u306f\u3001\u8ad6\u7406\u7684\u5224\u65ad\u4e0d\u53ef\u80fd\u3068\u306a\u308a\u307e\u3059\u3002<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u3042\u308b\u6587\u8108\u81ea\u7531\u6587\u6cd5$G$\u306f\u66d6\u6627\u6587\u6cd5\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n\n\n\n<li>\u3042\u308b\u6587\u8108\u81ea\u7531\u8a00\u8a9e$L$\u306f\u672c\u8cea\u66d6\u6627\u8a00\u8a9e\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n\n\n\n<li>\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u304b\u3064\u304c\u7a7a\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n\n\n\n<li>2\u3064\u306e\u6587\u8108\u81ea\u7531\u6587\u6cd5\u30fb\u8a00\u8a9e\u304c\u540c\u3058\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n\n\n\n<li>\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u306e\u88dc\u8a00\u8a9e\u304c\u7a7a\u304b\u3069\u3046\u304b\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n\n\n\n<li>\u3042\u308b\u6587\u8108\u81ea\u7531\u8a00\u8a9e$=\\Sigma^*$\u3092\u5224\u65ad\u3059\u308b\u3002<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">4.7 \u5c0f\u30c6\u30b9\u30c8<\/h2>\n\n\n\n<p>I. $L=\\{a^mb^n|m\\geq 0\\land 2m\\leq n\\leq3m\\}$\u306e\u4e00\u3064\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>II.$L=\\{w|w\\in(0+1)^*\\land 0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\}$\u306e\u4e00\u3064\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>III.$L=\\{w|w\\in(0+1)^*\\land 0,1$\u306e\u51fa\u73fe\u56de\u6570\u5dee\u306e\u7d76\u5bfe\u5024$= 2\\}$\u306e\u4e00\u3064\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.$L=\\{w|w\\in(0+1)^*\\land 0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u4e0d\u540c$\\}$\u306e\u4e00\u3064\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>V.$L=\\{0^n1^n|n\\geq 1\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VI.$\\Sigma=\\{0,1\\}$, $L=\\{ww^R|w\\in\\Sigma^*\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VII.$L=\\{w$\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>VIII.$L=\\{w$\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c\u3058\u3058\u3083\u306a\u3044$\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IX.$\\Sigma=\\{0,1\\}$, $L=\\{w|w $\u306e\u5168\u3066\u306e\u63a5\u982d\u90e8\u3067\u3001$a$\u306e\u51fa\u73fe\u56de\u6570\u306f$b$\u306e\u51fa\u73fe\u56de\u6570\u306e2\u500d\u3088\u308a\u5927$\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>X.$L=\\{0^n1^m|0\\leq n\\leq m\\leq2n\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XI.$\\Sigma=\\{a,b,c\\}$, $L=\\{a^mb^nc^k|a+2m=k\\}$\u306e\u4e00\u3064\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XII.$L=\\{0^n1^{n+2}\\}$\u306e\u4e00\u3064\u6c7a\u5b9a\u7684\u30d7\u30c3\u30b7\u30e5\u30c0\u30a6\u30f3\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>XIII.$L=\\{0^n1^n2^n\\}$\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XIV.$L=\\{0^n1^{n^2}\\}$\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XV.$\\Sigma=\\{0,1\\}$,$L=\\{ww|w\\in\\Sigma^*\\}$\u306f\u6587\u8108\u81ea\u7531\u8a00\u8a9e\u3067\u306a\u3044\u3092\u8a3c\u660e\u3002<\/p>\n\n\n\n<p>XVI.$\\Sigma=\\{a,b\\}$, $L=\\{w|w$\u3067$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\}$, \u4ee3\u6362$s(a)=L_a= {0^n 1^n | n \\geq 1}$<br>$s(b)=L_b= {ww^R | w\\in(0+1)^*}$<br>$s(L)$\u306e\u4e00\u3064\u6587\u8108\u81ea\u7531\u6587\u6cd5\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4.8 Answer<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\">4.9 \u691c\u5b9a\u554f\u984c<\/h2>\n\n\n\n<h1 class=\"wp-block-heading\">5. Turing \u30de\u30b7\u30fc\u30f3<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">5.1 \u6a19\u6e96 Turing \u30de\u30b7\u30fc\u30f3<\/h2>\n\n\n\n<p>$TM$\u306f\u6709\u9650\u5185\u90e8\u72b6\u614b$Q$\u3092\u6709\u3057\u3001\u5165\u529b\u6587\u5b57\u5217\u3092\u8f09\u305b\u305f\u30de\u30b9\u76ee\u306b\u533a\u5207\u3089\u308c\u305f\u7247\u5074(\u307e\u305f\u4e21\u5074\u7121\u9650)\u30c6\u30fc\u30d7\u3092\u30d8\u30c3\u30c9\u3092\u8a18\u53f7\u3092\u8aad\u307f\u3001\u5185\u90e8\u72b6\u614b\u306b\u5fdc\u3058\u3066\u30c6\u30fc\u30d7\u8a18\u53f7\u3092\u66f8\u304d\u63db\u3048\u30d8\u30c3\u30c9\u3092\u5de6\u53f3\u306b\u79fb\u52d5\u3055\u305b\u306a\u304c\u3089\u52d5\u4f5c\u3092\u7e70\u308a\u8fd4\u3059\u3002\u6700\u521d\u306b\u4e0e\u3048\u305f\u5165\u529b\u6587\u5b57\u5217\u306e\u4ee5\u5916\u306e\u30c6\u30fc\u30d7\u306e\u30de\u30b9\u76ee\u306f\u7a7a\u767d\u8a18\u53f7\u3067\u57cb\u3081\u3089\u308c\u3066\u3044\u308b\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.1.1 \u57fa\u672c\u6982\u5ff5<\/h3>\n\n\n\n<p>$TM=(Q,\\Sigma,\\Gamma,\\delta,q_0,B,F)$<\/p>\n\n\n\n<p>\u3053\u3053\u3067\u3001$Q$\u306f\u72b6\u614b\u96c6\u5408\u3001$\\Sigma$\u306f\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\Gamma$\u306f\u30c6\u30fc\u30d7\u30a2\u30eb\u30d5\u30a1\u30d9\u30c3\u30c8\u3001$\\delta$\u306f\u72b6\u614b\u9077\u79fb\u95a2\u6570\u3001$q_0$\u306f\u521d\u671f\u72b6\u614b\u3001$B$\u30d6\u30e9\u30f3\u30af\u8a18\u53f7\u3001$F$\u306f\u53d7\u7406\u72b6\u614b\u96c6\u5408\u3002\u5165\u529b\u306f\u3059\u3067\u306b\u5de6\u53f3\u7121\u9650\u9577\u30c6\u30fc\u30d7\u306b\u66f8\u304b\u308c\u305f\u3002\u30d8\u30c3\u30c9\u306e\u521d\u671f\u4f4d\u7f6e\u306f\u7b2c\u4e00\u5165\u529b\u8a18\u53f7\u306e\u4e0a\u3002<\/p>\n\n\n\n<p>$\\delta: Q\\times\\Gamma\\rightarrow Q\\times\\Gamma\\times\\{L,R\\}$\u3002<\/p>\n\n\n\n<p>\u72b6\u614b\u9077\u79fb\u8868\u8a18$X\/Y,L$\u306f\u3001<br>\u30d8\u30c3\u30c9\u304c\u30c6\u30fc\u30d7\u8a18\u53f7$X$\u3092\u8aad\u3080\u3068\u3001\u30c6\u30fc\u30d7\u8a18\u53f7$X$\u3092$Y$\u306b\u66f8\u304d\u63db\u3048\u3066\u30d8\u30c3\u30c9\u3092\u5de6\u306b\u79fb\u52d5\u3059\u308b\u3002<\/p>\n\n\n\n<p>\u5373\u5ea7\u89e3\u91c8<br>$X_1,X_2,\\cdots,X_{i-1},pX_i,X_{i+1}\\cdots,X_n$<br>\u30d8\u30c3\u30c9\u306f\u3044\u3064\u3082\u72b6\u614b\u306e\u53f3\u5074\u306b\u3042\u308a\u3002<br>\u5373\u5ea7\u89e3\u91c8\u306e\u72b6\u614b\u9077\u79fb<br>\u4f8b\uff1a$X_1,X_2,\\cdots,X_{i-1},pX_i,X_{i+1}\\cdots,X_n$ $\\vdash$ $X_1,X_2,\\cdots,X_{i-1},X_i,qX_{i+1}\\cdots,X_n$<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.1.2 \u5165\u529b\u53d7\u7406<\/h3>\n\n\n\n<p>\u53d7\u7406\u72b6\u614b\u306b\u9054\u3057\u306a\u3044\u3068\u304d\u3001TM \u306f\u52d5\u4f5c\u3092\u505c\u6b62\u3059\u308b\u3002\u3053\u306e\u6642\u3001\u5165\u529b\u306f\u53d7\u7406\u3055\u308c\u306a\u3044\u3002<br>\u53d7\u7406\u72b6\u614b\u306b\u9054\u3057\u305f\u3068\u304d\u3001TM \u306f\u5165\u529b\u3092\u53d7\u7406\u3057\u3066\u8a08\u7b97\u3092\u505c\u6b62\u3057\u305f\u3068\u3044\u3046\u3002<br>TM \u304c\u5165\u529b\u3092\u53d7\u7406\u3057\u306a\u3044\u3068\u304d\u306f\u3001\u304b\u306a\u3089\u305a\u3057\u3082\u505c\u6b62\u3059\u308b\u308f\u3051\u3067\u306f\u306a\u3044\u3002\uff08\u3053\u308c\u306f\u8ad6\u7406\u7684\u5224\u65ad\u4e0d\u53ef\u80fd\u554f\u984c\uff09<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.1.3 Turing \u30de\u30b7\u30fc\u30f3\u306e\u8a00\u8a9e<\/h3>\n\n\n\n<p>\u3042\u308bTuring \u30de\u30b7\u30fc\u30f3\u306e\u8a00\u8a9e\u306f\u5e30\u7d0d\u7684\u53ef\u7b97\u8a00\u8a9e\u3068\u3044\u3044\u3002<br>\u7279\u306b\u3001\u3069\u3093\u306a\u5165\u529b\u3067\u3082\u3042\u308bTM\u306e\u52d5\u4f5c\u3092\u505c\u6b62\u3055\u305b\u308b\u8a00\u8a9e\u306f\u5e30\u7d0d\u8a00\u8a9e\u3001\u3042\u308b\u3044\u306f\u6c7a\u5b9a\u53ef\u80fd\u3068\u3044\u3044\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">5.2 \u4ed6\u306e Turing \u30de\u30b7\u30fc\u30f3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">5.2.1 Multi-track\u5f0f<\/h3>\n\n\n\n<p>\u30d8\u30c3\u30c9\u306f\u4e00\u5ea6\u306b\u8907\u6570\u306e\u6587\u5b57\u3092\u8aad\u307f\u53d6\u308b\u3001\u66f8\u304d\u8fbc\u3080\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.2.2 Multi-tape\u5f0f<\/h3>\n\n\n\n<p>\u8907\u6570\u306e\u30d8\u30c3\u30c9\u3042\u308a\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.2.3 \u975e\u6c7a\u5b9a\u7684<\/h3>\n\n\n\n<p>DFA\u3068NFA\u306e\u95a2\u4fc2\u306b\u4f3c\u3066\u308b\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.2.4 \u30c6\u30fc\u30d7\u304c\u534a\u7121\u9650\u7684<\/h3>\n\n\n\n<p>\u30c6\u30fc\u30d7\u304c\u5de6\u7121\u9650\u9577\u3001\u307e\u305f\u306f\u53f3\u7121\u9650\u9577\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.2.4 \u8907\u6570\u30b9\u30bf\u30c3\u30afPDA<\/h3>\n\n\n\n<p>\u8907\u6570\u306e\u30b9\u30bf\u30c3\u30af\u3092\u6301\u3064PDA\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">5.3 Turing \u30de\u30b7\u30fc\u30f3\u306e\u8868\u73fe\u80fd\u529b<\/h2>\n\n\n\n<p>5.2\u306e\u69d8\u3005\u306a\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306f\u30015.1\u306e Turing \u30de\u30b7\u30fc\u30f3\u3068\u540c\u5024\u3002<\/p>\n\n\n\n<p>\u8868\u73fe\u80fd\u529b\u306f\u5e30\u7d0d\u7684\u53ef\u7b97\u8a00\u8a9e\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">5.4 \u5c0f\u30c6\u30b9\u30c8<\/h2>\n\n\n\n<p>I.$L=\\{0^n1^n|n\\geq 1\\}$\u306e\u4e00\u3064 Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>II.$L=\\{0^n1^n2^n|n\\geq 1\\}$\u306e\u4e00\u3064 Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>III.$L=\\{w$\u3067\u3001$0,1$\u306e\u51fa\u73fe\u56de\u6570\u304c\u540c$\\}$\u306e\u4e00\u3064 Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.\u300e2\u9032\u6570+1\u300f\u306e Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002(\u4f8b\uff1a$BBp\\$1111BB\\vdash BBq\\$10000BB$)<\/p>\n\n\n\n<p>IV.\u300e\u6b63\u6e1b\u7b97\u300f\u306e Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002(\u4f8b\uff1a<br>$BBp00001000BB\\vdash BBq0BB$  (4-3=1),<br>$BBp001000BB\\vdash BBqBB$  (2-3=0))<\/p>\n\n\n\n<p>IV.$\\Sigma=\\{a,b\\}$, $L=\\{wcw|w\\in\\Sigma^*\\}$\u306e\u4e00\u30642 track \u5f0f Turing \u30de\u30b7\u30fc\u30f3\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.$L=\\{a^nb^nc^n|n\\geq0\\}$\u306e\u4e00\u30642\u30b9\u30bf\u30c3\u30afPDA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<p>IV.$L=\\{a^nb^nc^nd^ne^n|n\\geq0\\}$\u306e\u4e00\u30642\u30b9\u30bf\u30c3\u30afPDA\u3092\u6c42\u3081\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">5.5 Answer<\/h2>\n\n\n\n<h2 class=\"wp-block-heading\">5.6 \u691c\u5b9a\u554f\u984c<\/h2>\n","protected":false},"excerpt":{"rendered":"<p>\u5f62\u5f0f\u8a00\u8a9e\u3068\u30aa\u30fc\u30c8\u30de\u30c8\u30f3\u306e\u307e\u3068\u3081\u3001\u304a\u3088\u3073\u7df4\u7fd2\u554f\u984c\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"swell_btn_cv_data":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[10],"tags":[],"class_list":["post-282","post","type-post","status-publish","format-standard","hentry","category-flaa"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/282","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/comments?post=282"}],"version-history":[{"count":201,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/282\/revisions"}],"predecessor-version":[{"id":687,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/282\/revisions\/687"}],"wp:attachment":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/media?parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/categories?post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/tags?post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}