Nevezzünk egy M véges automatához egy u szót irányító szónak, ha minden p,q állapotra pu = qu, vagyis ha az automata bármely állapotjában is megkapja az u szót, egy konkrét állapotba kerül bele az indulástól függetlenül. Az M automata irányítható, ha van hozzá iranyító szó. Jelölje ekkor d(M) a(z egyik) legrövidebb irányító szó hosszát, d(n) pedig a max{d(M): M iranyítható, n-állapotú automata} mennyiséget.
Jan Cerny 1964-ben minden n>0-ra megadott egy-egy olyan n-állapotos irányítható M_n automatát az {a,b} input ábc fölött, melyre d(M_n)=(n-1)^2 (így tehát d(n)>=(n-1)^2) és megfogalmazta azt az azóta is nyitott sejtését, hogy itt igazáből egyenlőség van, vagyis d(n)=(n-1)^2. Átfogalmazva az állítás az, hogy ha vesszük az {1,..,n} halmaz transzformációinak egy tetszőleges {f1,..,fk} halmazát úgy, hogy valamely konstans függvény előáll valamilyen kompozíciójukként, akkor mar egy max. (n-1)^2-tényezős kompozícióként is előáll egy konstans függvény.
Azt, hogy d(n) = Ordo( n^3 ), nem nehéz látni, de megnézzük. Ezt követően megnézzük, hogy a sejtés milyen speciális automataosztályokra bizonyult igaznak, illetőleg szemezgetünk ilyen típusú eredmények közül. Alapul Avraham Trahtman "Some Aspects of Synchronization of DFA" cikkét vesszük, megjelent 2008. szeptemberben, a Journal of Computer Science and Technology lapban.
Ha lesz időnk, beszélek a kérdés kiterjesztéseiről nemdeterminisztikus automaták esetére is.
Minden érdeklődőt szeretettel várunk,
Péter