Exercises

Mikołaj Bojańczyk

zajęcia / courses

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