{"id":1046,"date":"2016-03-02T17:20:16","date_gmt":"2016-03-02T16:20:16","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1046"},"modified":"2016-03-02T17:21:16","modified_gmt":"2016-03-02T16:21:16","slug":"exercise","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/1-introduction-to-monoids\/exercise","title":{"rendered":"Exercises"},"content":{"rendered":"

Exercise.\u00a0<\/strong>Call an element \"e\" in a monoid idempotent if it satisfies \"e = ee\".\u00a0Show that for every finite monoid \"M\" and every \"m \in M\", there is a number \"k\" such that \"m^k\" is an idempotent.<\/p>\n

Exercise.\u00a0<\/strong>Show a language where the monoid is exponentially bigger\u00a0than the (minimal) DFA.<\/p>\n

Exercise.\u00a0<\/strong>Show a language where the monoid is exponentially bigger than the (minimal) DFA, and also exponentially bigger than the (minimal) right-to-left DFA.<\/p>\n

Exercise.\u00a0<\/strong>Given an example of a monoid homomorphism \"h : M \to N\" and a monoid \"K \supseteq M\" such that \"h\" cannot be extended to \"K\".<\/p>\n

Exercise.\u00a0<\/strong>We say that a monoid \"M\" contains a group if there is some subset \"G \subseteq M\" such that \"G\" forms a group, with the multiplication operation inherited from \"M\", but not necessarily the identity. Show that if a finite monoid contains a group, then it contains a cyclic group.<\/p>\n

Exercise.\u00a0<\/strong>Show that the number of monoids of size \"n\" is at least exponential in \"n\".<\/p>\n

Exercise.\u00a0<\/strong>Let \"h : \Sigma^* \to M\" be a homomorphism into a finite monoid. Show that there is some \"f : \Nat \to \Nat\" such that for every \"n \in \Nat\", every word \"w\" of length at least \"f(n)\" admits a factorisation <\/p>\n

  <\/span>   <\/span>\"\[w = w_0 w_1 \cdots w_n w_{n+1}\]\"<\/p>\n

such that all of the words \"w_1,\ldots,w_n\" have the same image under \"h\", and this image is idempotent.<\/p>\n

Exercise. <\/strong>For every \"k \in \Nat\", give an example of a monoid \"M\" where the function \"f\" from the previous exercise satisfies <\/p>\n

  <\/span>   <\/span>\"\[f(n) \ge n^k.\]\"<\/p>\n

 <\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Exercise.\u00a0Call an element in a monoid idempotent if it satisfies .\u00a0Show that for every finite monoid and every , there is a number such that is an idempotent. Exercise.\u00a0Show a language where the monoid is exponentially bigger\u00a0than the (minimal) DFA. Exercise.\u00a0Show a language where the monoid is exponentially bigger than the (minimal) DFA, and also […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":198,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1046","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1046"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=1046"}],"version-history":[{"count":7,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1046\/revisions"}],"predecessor-version":[{"id":1053,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1046\/revisions\/1053"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/198"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}