hidden - assigned and confirmed by the Study Dept.
Date of registration:
10.10.2016
Date of assignment:
29.06.2017
Confirmed by Study dept. on:
17.07.2017
Date and time of defence:
14.09.2017 00:00
Date of electronic submission:
21.07.2017
Date of submission of printed version:
21.07.2017
Date of proceeded defence:
14.09.2017
Opponents:
doc. Mgr. et Mgr. Jan Žemlička, Ph.D.
Guidelines
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.
References
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).
Preliminary scope of work
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?
- assigned and confirmed by the Study Dept.