{"id":301,"date":"2015-04-24T18:37:01","date_gmt":"2015-04-24T16:37:01","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=301"},"modified":"2015-09-22T16:29:10","modified_gmt":"2015-09-22T14:29:10","slug":"exercises","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/exercises","title":{"rendered":"Exercises"},"content":{"rendered":"<p><strong>Idempotent semigroup.\u00a0<\/strong>Call a semigroup\u00a0<em>idempotent<\/em> if every element is idempotent.<\/p>\n<p>0. Show that if a semigroup\u00a0is idempotent and <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-8255b8636497b6ab6c2a22220b1ca86c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#74;&#106;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"13\" style=\"vertical-align: -1px;\"\/>-trivial, then it is commutative.<\/p>\n<p>1. Prove that if a semigroup\u00a0is idempotent, then every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-8255b8636497b6ab6c2a22220b1ca86c_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#92;&#74;&#106;\" title=\"Rendered by QuickLaTeX.com\" height=\"12\" width=\"13\" style=\"vertical-align: -1px;\"\/>-class is closed under multiplication (i.e. it is a sub-semigroup)<\/p>\n<p>2. Prove that for every <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-1581bd603826320b358d867162d09127_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"7\" width=\"9\" style=\"vertical-align: 0px;\"\/> there are finitely many idempotent semigroups with <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-1581bd603826320b358d867162d09127_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#110;\" title=\"Rendered by QuickLaTeX.com\" height=\"7\" width=\"9\" style=\"vertical-align: 0px;\"\/> generators.<\/p>\n<p>&nbsp;<\/p>\n<p><b>Strongly connected automata.\u00a0<\/b>Let <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-a761508c40fd598ec631e883a758a160_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;&#32;&#92;&#115;&#117;&#98;&#115;&#101;&#116;&#101;&#113;&#32;&#92;&#83;&#105;&#103;&#109;&#97;&#94;&#42;\" title=\"Rendered by QuickLaTeX.com\" height=\"14\" width=\"48\" style=\"vertical-align: -2px;\"\/> be a regular language with the following properties:<\/p>\n<ul>\n<li>the\u00a0minimal DFA is strongly connected (i.e. every state is reachable from every other state);<\/li>\n<li>the minimal DFA of the reverse of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-c2289d1b720dbeb200c7be3944b43068_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"10\" style=\"vertical-align: 0px;\"\/> is strongly connected;<\/li>\n<li>the syntactic monoid of <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-c2289d1b720dbeb200c7be3944b43068_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"10\" style=\"vertical-align: 0px;\"\/> is aperiodic.<\/li>\n<\/ul>\n<p>Prove that <img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-c2289d1b720dbeb200c7be3944b43068_l3.png\" class=\"ql-img-inline-formula quicklatex-auto-format\" alt=\"&#76;\" title=\"Rendered by QuickLaTeX.com\" height=\"11\" width=\"10\" style=\"vertical-align: 0px;\"\/> is trivial, i.e. empty or full.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Idempotent semigroup.\u00a0Call a semigroup\u00a0idempotent if every element is idempotent. 0. Show that if a semigroup\u00a0is idempotent and -trivial, then it is commutative. 1. Prove that if a semigroup\u00a0is idempotent, then every -class is closed under multiplication (i.e. it is a sub-semigroup) 2. Prove that for every there are finitely many idempotent semigroups with generators. &nbsp; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":42,"menu_order":2,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-301","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/301"}],"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=301"}],"version-history":[{"count":4,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/301\/revisions"}],"predecessor-version":[{"id":528,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/301\/revisions\/528"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/42"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=301"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}