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

## Leave a Reply