Mikołaj Bojańczyk

Exercise. Call an element e in a monoid idempotent if it satisfies e = ee. Show that for every finite monoid M and every m \in M, there is a number k such that m^k 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 h : M \to N and a monoid K \supseteq M such that h cannot be extended to K.

Exercise. 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.

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

Exercise. 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

    \[w = w_0 w_1 \cdots w_n w_{n+1}\]

such that all of the words w_1,\ldots,w_n have the same image under h, and this image is idempotent.

Exercise. For every k \in \Nat, give an example of a monoid M where the function f from the previous exercise satisfies

    \[f(n) \ge n^k.\]




Leave a Reply

Your email address will not be published.