Postup

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
  • po skončení vezmu slova vedoucí z finálových stavů (vedou do počátečního stavu) a vyberu nejdelší