Student se seznámí s problémem hvězdné výšky regulárních jazyků. Popíše konstrukci jazyka s danou hvězdnou výškou.
Seznam odborné literatury
Lawrence C. Eggan. Transition graphs and the star-height of regular events Michigan Mathematical Journal 10 (4):385–397, 1963.
F. Dejean and M. P. Schützenberger. On a Question of Eggan. Information and Control, 9:23–25, 1966.
Jacques Sakarovitch. Elements of Automata Theory, Cambridge university press (2009).
Předběžná náplň práce
Jedná se o starý a zřejmě těžký problém týkající se struktury regulárních množin. Formulace problému a některé základní poznatky jsou ovšem velmi jednoduché, což činí problém atraktivním. Konkrétně se jedná o otázku: lze každý regulární výraz přepsat tak, aby obsahoval jen omezený počet do sebe vnořených Kleenových hvězd?