Mikołaj Bojańczyk

Exercise. Call an element in a monoid idempotent if it satisfies . Show that for every finite monoid and every , there is a number such that is an idempotent.

Exercise. Show a language where the monoid is exponentially bigger than the (minimal) DFA.

Exercise. Show a language where the monoid is exponentially bigger than the (minimal) DFA, and also exponentially bigger than the (minimal) right-to-left DFA.

Exercise. Given an example of a monoid homomorphism and a monoid such that cannot be extended to .

Exercise. We say that a monoid contains a group if there is some subset such that forms a group, with the multiplication operation inherited from , but not necessarily the identity. Show that if a finite monoid contains a group, then it contains a cyclic group.

Exercise. Show that the number of monoids of size is at least exponential in .

Exercise. Let be a homomorphism into a finite monoid. Show that there is some such that for every , every word of length at least admits a factorisation such that all of the words have the same image under , and this image is idempotent.

Exercise. For every , give an example of a monoid where the function from the previous exercise satisfies 