{"id":422,"date":"2018-10-18T12:21:11","date_gmt":"2018-10-18T12:21:11","guid":{"rendered":"http:\/\/adrianbell.me\/?p=422"},"modified":"2018-10-18T12:21:11","modified_gmt":"2018-10-18T12:21:11","slug":"pumping-lemma","status":"publish","type":"post","link":"https:\/\/adrianbell.me\/?p=422","title":{"rendered":"Pumping Lemma"},"content":{"rendered":"\r\n\r\nWay way off the beaten path here, but this is the best example of usage of the pumping lemma I've seen. Just need somewhere to put it...\r\n\r\n\r\n\r\n\r\n\r\nThe below is taken from <a href=\"https:\/\/www.tutorialspoint.com\/automata_theory\/automata_theory_quick_guide.htm\">here<\/a>.\r\n\r\n<strong>Theorem:<\/strong>\r\n\r\nLet <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> be a regular language, and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-d4b432605ef5750fdc8e364f5bc8beea_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"13\" style=\"vertical-align: 0px;\"\/> be a string. Then there exists a constant <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-276a76eafbebc4494deafceec7cc4ddd_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#99;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"8\" style=\"vertical-align: 0px;\"\/> s.t. <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-7edc265d738396e91c88b83259d8b7b7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#102;&#111;&#114;&#97;&#108;&#108;&#32;&#119;&#32;&#92;&#105;&#110;&#32;&#76;&#44;&#32;&#124;&#119;&#124;&#32;&#92;&#103;&#101;&#113;&#32;&#99;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"119\" style=\"vertical-align: -5px;\"\/>.\r\n\r\nWe can break <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-d4b432605ef5750fdc8e364f5bc8beea_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"13\" style=\"vertical-align: 0px;\"\/> into three strings, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-f2eac6aea735b177224040ddf5166531_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;&#61;&#120;&#121;&#122;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"65\" style=\"vertical-align: -4px;\"\/>, s.t.:\r\n<ul>\r\n \t<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-bd3b1f4ea7de8d49d5f3ed0f2ec05b57_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#121;&#124;&#32;&#62;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"50\" style=\"vertical-align: -5px;\"\/><\/li>\r\n \t<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-8c825054403340011202362bf4319528_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#120;&#121;&#124;&#32;&#92;&#108;&#101;&#113;&#32;&#99;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"59\" style=\"vertical-align: -5px;\"\/><\/li>\r\n \t<li><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-8da8bcd6ca56f625e706d0a781bad3a7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#102;&#111;&#114;&#97;&#108;&#108;&#32;&#107;&#32;&#92;&#103;&#101;&#113;&#32;&#48;&#44;&#32;&#120;&#121;&#94;&#123;&#107;&#125;&#122;&#32;&#92;&#105;&#110;&#32;&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"130\" style=\"vertical-align: -4px;\"\/><\/li>\r\n<\/ul>\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n<strong>Method to prove that a language <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is not regular:<\/strong>\r\n<ul>\r\n \t<li>At first, we have to assume that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is regular.<\/li>\r\n \t<li>So, the pumping lemma should hold for <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>.<\/li>\r\n \t<li>Use the pumping lemma to obtain a contradiction:<\/li>\r\n \t<li>Select <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-d4b432605ef5750fdc8e364f5bc8beea_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"13\" style=\"vertical-align: 0px;\"\/> s.t. <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-9aefd311f48bc50a7f60457d35837453_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#119;&#124;&#32;&#92;&#103;&#101;&#113;&#32;&#99;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"53\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>Select <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-38461fc041e953482219abf5d4cce1cb_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#121;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: -4px;\"\/> s.t. <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-75cdabef363b62a46f51f31c306eaa8f_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#121;&#124;&#32;&#92;&#103;&#101;&#113;&#32;&#49;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"49\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>Select <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-7e5fbfa0bbbd9f3051cd156a0f1b5e31_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"10\" style=\"vertical-align: 0px;\"\/> s.t. <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-8c825054403340011202362bf4319528_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#120;&#121;&#124;&#32;&#92;&#108;&#101;&#113;&#32;&#99;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"59\" style=\"vertical-align: -5px;\"\/><\/li>\r\n \t<li>Assign the remaining string to <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-ec5583fa081a1e03212c151e3c222412_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#122;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"9\" style=\"vertical-align: 0px;\"\/>.<\/li>\r\n \t<li>Select <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-d42bc2203d6f76ad01b27ac9acc0bee1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"9\" style=\"vertical-align: 0px;\"\/> s.t. the resulting string is not in <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/>.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\n<strong>Problem:<\/strong>\r\n\r\nProve that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-2f332a7773f6b964e315403c23af93aa_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;&#61;&#92;&#123;&#97;&#94;&#123;&#105;&#125;&#98;&#94;&#123;&#105;&#125;&#32;&#124;&#32;&#105;&#32;&#92;&#103;&#101;&#113;&#32;&#48;&#92;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"124\" style=\"vertical-align: -5px;\"\/> is not regular.\r\n\r\n<strong>Solution:<\/strong>\r\n<ul>\r\n \t<li>At first, we assume that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is regular and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-ec4217f4fa5fcd92a9edceba0e708cf7_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"8\" width=\"11\" style=\"vertical-align: 0px;\"\/> is the number of states.<\/li>\r\n \t<li>Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-e724f0ea83a697c11939b69cd94f6387_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;&#61;&#97;&#94;&#123;&#110;&#125;&#98;&#94;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"71\" style=\"vertical-align: 0px;\"\/>. Thus <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-f7a0c8fa85cdde372e04623061edefc1_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#119;&#124;&#61;&#50;&#110;&#92;&#103;&#101;&#113;&#32;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"99\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>By the pumping lemma, let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-f2eac6aea735b177224040ddf5166531_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#119;&#61;&#120;&#121;&#122;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"65\" style=\"vertical-align: -4px;\"\/>, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-cd3f324c03e0b607a996fe5c960f36ab_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#120;&#121;&#124;&#32;&#92;&#108;&#101;&#113;&#32;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"62\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-0c31a302650d170ee3e042dc5b4d7bc5_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#61;&#97;&#94;&#123;&#112;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"50\" style=\"vertical-align: 0px;\"\/>,\u00a0<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-fb0c32b700c0e9f96cc2a56977dc08ef_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#121;&#61;&#97;&#94;&#123;&#113;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"16\" width=\"49\" style=\"vertical-align: -4px;\"\/>, and\u00a0<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-0ececa21189c627131a3ed0b5e786601_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#122;&#61;&#97;&#94;&#123;&#114;&#125;&#98;&#94;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"65\" style=\"vertical-align: 0px;\"\/>, where <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-8cecbf3342ab560f0bc41f99d11142c2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#43;&#113;&#43;&#114;&#61;&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"15\" width=\"105\" style=\"vertical-align: -4px;\"\/>, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48f65532f1690076ba6258e476e45b90_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#112;&#32;&#92;&#110;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"43\" style=\"vertical-align: -4px;\"\/>,\u00a0<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-7a277285f6edc01b5d85405db9aadbc9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#113;&#32;&#92;&#110;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"41\" style=\"vertical-align: -4px;\"\/>,\u00a0<img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-086d8910e6d079cd38cfae443c426858_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#114;&#32;&#92;&#110;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"41\" style=\"vertical-align: -4px;\"\/>. Thusly <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-74af339a112f83a46812d582833501f2_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#124;&#121;&#124;&#32;&#92;&#110;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"50\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-9f71b687cf7d563e45e43df91e290531_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#107;&#61;&#50;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"41\" style=\"vertical-align: 0px;\"\/>. Then <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-e40a8d73eff92f8862b66ad2e08de1d6_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#121;&#94;&#123;&#50;&#125;&#122;&#61;&#97;&#94;&#123;&#112;&#125;&#97;&#94;&#123;&#50;&#113;&#125;&#97;&#94;&#123;&#114;&#125;&#98;&#94;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"133\" style=\"vertical-align: -4px;\"\/>.<\/li>\r\n \t<li>Number of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-748347aedf8966d9b28a9e00f6c25222_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#92;&#116;&#101;&#120;&#116;&#123;&#39;&#115;&#125;&#61;&#40;&#112;&#43;&#50;&#113;&#43;&#114;&#41;&#32;&#61;&#32;&#40;&#112;&#43;&#113;&#43;&#114;&#41;&#43;&#113;&#61;&#110;&#43;&#113;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"338\" style=\"vertical-align: -5px;\"\/>.<\/li>\r\n \t<li>Hence, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-0af4197cf3278577082927410af8e705_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#121;&#94;&#123;&#50;&#125;&#122;&#61;&#97;&#94;&#123;&#110;&#43;&#113;&#125;&#98;&#94;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"112\" style=\"vertical-align: -4px;\"\/>. Since <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-5435213cba330b806da259e3934611d9_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#113;&#92;&#110;&#101;&#113;&#32;&#48;\" title=\"Rendered by QuickLaTeX.com\" height=\"17\" width=\"41\" style=\"vertical-align: -4px;\"\/>, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-ef29d4c730dbe819684a1ab3c7cc99ff_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#121;&#94;&#123;&#50;&#125;&#122;\" title=\"Rendered by QuickLaTeX.com\" height=\"19\" width=\"36\" style=\"vertical-align: -4px;\"\/> is not of the form <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-bc5fb92b8b40231b299c16277368d72c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#97;&#94;&#123;&#110;&#125;&#98;&#94;&#123;&#110;&#125;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"35\" style=\"vertical-align: 0px;\"\/>!!!!!!!!!!!!!!!<\/li>\r\n \t<li>Thus, <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-0311453de949c43a23212d9e4d3d9c04_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#120;&#121;&#94;&#123;&#50;&#125;&#122;&#32;&#92;&#110;&#111;&#116;&#105;&#110;&#32;&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"20\" width=\"70\" style=\"vertical-align: -5px;\"\/>. Hence <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/adrianbell.me\/wp-content\/ql-cache\/quicklatex.com-48d71fca322532f0abc2c4ad2cf98154_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"12\" style=\"vertical-align: 0px;\"\/> is not regular.<\/li>\r\n<\/ul>\r\n\r\n\r\n\r\n\r\n","protected":false},"excerpt":{"rendered":"<p>Way way off the beaten path here, but this is the best example of usage of the pumping lemma I've seen. Just need somewhere to put it... The below is taken from here. Theorem: Let be a regular language, and be a string. Then there exists a constant s.t. . We can break into three &hellip; <a href=\"https:\/\/adrianbell.me\/?p=422\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Pumping Lemma<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[33,14,32],"tags":[34,35,36],"class_list":["post-422","post","type-post","status-publish","format-standard","hentry","category-automata-theory","category-proofs","category-pure-maths","tag-automata-theory","tag-pumping-lemma","tag-regular-language"],"_links":{"self":[{"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/posts\/422","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/adrianbell.me\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=422"}],"version-history":[{"count":22,"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/posts\/422\/revisions"}],"predecessor-version":[{"id":445,"href":"https:\/\/adrianbell.me\/index.php?rest_route=\/wp\/v2\/posts\/422\/revisions\/445"}],"wp:attachment":[{"href":"https:\/\/adrianbell.me\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=422"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/adrianbell.me\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=422"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/adrianbell.me\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=422"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}