Matematické Fórum

První by nemělo být těžké vygooglit, nechci zde dávat odkaz opět na stejná skripta (Křetínský, Černá, Kučera: Formální jazyky a automaty).

Druhý je zajímavější.
Funkce je transformace na množině stavů, která vznikne složením transformací , kde jsou písmenka slova . To, co se po nás chce, je ukázat, že každou transformaci stavů lze složit z několika transformací, které odpovídají písmenům. Pokud bychom mohli mít písmen kolik chceme, třeba n!, pak není potřeba nic skládat, každá transformace odpovídá samotnému písmenu a na nás se smějí dva body (pokud to trochu zformalizujeme). Pokud máme abecedu omezenou, musíme ukázat, že každý (konečný) transformační monoid má konstantně mnoho generátorů. Jistě víme, že grupa prmutací je generována cyklem (1 2) a cyklem (1 2 3 ... n). Když k nim přidáme ještě jednu transformaci, vygenerujeme celý monoid (s řádným důkazem, který si dovluji vynechat) a jsme o tři body bohatší.

Chytré profesory zdravím, a doufám, že jsem to nepřehnal.