Asi to jde udělat jinak i lépe, četl jsem o postupu kdy se to zvládne pouze během jednoho průchodu DFS, ale úplně mi to nešlo do hlavy, tak prezentuju svoje řešení, je to také 10/10:
Nejdříve zjištění, jestli automat přijímá FINITE nebo INFINITE jazyk
DFS z počátečního stavu (explicitní zásobník a while smyčka)
Pokud narazím na cyklus, zapíšu si u všech stavů v tom cyklu, že jsou součástí cyklu (pro připomenutí - stavy cyklu se nachází na zásobníku v části odshora až do výskytu toho stavu, na který jsme narazili a je OPEN)
Pokud narazím na konečný stav:
ke všem stavům na zásobníku zapíšu, že vedou do konečného stavu (pozor - když narazím na stav, který již vede do konečného, přestanu se zapisováním, protože všechny stavy předtím to mají již nastavené někdy odminula)
pokud je aktuální stav součástí cyklu a zároveň vede do konečného stavu, přeruším DFS a jdu hledat nejkratší slovo, protože mám INFINITE jazyk
pokud DFS doběhne bez přerušení, mám FINITE jazyk a jdu hledat nejkratší slovo
Nejkratší slovo (INFINITE jazyk):
BFS z počátečního stavu
U stavů si pamatuju, jakým terminálem jsem do nich přišel (a odkud) nebo jakým slovem se do nich dá dostat
Když dojdu do konečného stavu, skončím (nemá smysl pokračovat a hledat cestu do dalších konečných stavů, protože do nich nutně vede delší cesta /slovo/ než do tohohle)
Nejdelší slovo (FINITE jazyk):
DFS z počátečního stavu
Nechodím do stavů, které jsou součástí cyklu
U každého stavu si pamatuju příchozí vzdálenost od počátečního + to samé jako v INFINITE jazyku
Do stavu jdu jen v tom případě, že bych mu zvětšil příchozí vzdálenost nebo pokud je stejná, tak terminál/slovo
DFS nechám doběhnout celý, nijak nepřerušuju