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