Tento projekt je vhodný zejména pro studenty, kteří navštěvují či navštěvovali kurzy IB102 nebo IB005. Teoretické základy nutné k pochopení zadání však nejsou nijak složité a ten, kdo je pochopí před zapsáním výše jmenovaných předmětů, si jistě nijak neuškodí.

Co jsou to konečné automaty se dozvíte např. na Wikipedii či ve studijním textu k formálům (zejména kapitoly 1.1, 2.1, 2.2.1, 2.2.2). Pojem konečného automatu (Finite Automaton, FA) se pokusíme nastínit i zde.

Konečný automat si můžete představit jako orientovaný multigraf s konečným počtem vrcholů, kterým říkáme stavy. Místo grafu mluvíme o multigrafu, což znamená jen to, že mezi dvěma stavy může být více hran (těm říkáme přechody; vedou vždy z nějakého stavu do jiného, proto je graf orientovaný), které odlišujeme návěštím. Návěští je popisek sestávající z jednoho písmena tzv. abecedy, což je nějaká konečná množina, jejíž prvky obvykle označujeme skutečnými písmeny. Některé stavy označíme za koncové, jeden stav vybereme za počáteční (může být zároveň i koncovým).

Výpočet nad slovem x₁…x_n je posloupnost stavů s₁…s_n+1 takových, že s₁ je počáteční a z každého stavu s_i vede přechod do s_i+1 s návěštím x_i. Slovo tedy řídí výpočet tím, že automat z něj před každým přechodem přečte jedno další písmeno a podle něj určuje možné přechody z aktuálního stavu. Je-li navíc s_n koncový, pak je výpočet akceptující. Předpokládáme, že z počátečního stavu existuje do každého dalšího stavu konečná posloupnost přechodů, stavy takto nedosažitelné jsou zanedbatelné, protože do automatu nepřidávají žádný nový výpočet. Automat je deterministický, existuje-li ke každému slovu nejvýše jeden výpočet nad ním. To je ekvivalentní tomu, že z každého stavu existuje pod každým návěštím nejvýše jeden přechod. Slovo je akceptováno automatem, existuje-li akceptující výpočet nad tímto slovem. Automat je úplný, existuje-li ke každému slovu alespoň jeden výpočet nad ním.

Příklad takového automatu vídíte na následujícím obrázku. Stavy jsou {r,s,t}, počáteční je r, koncové r a t, abeceda je {a,b}. Automat je deterministický, akceptovaná slova jsou právě prázdné slovo (slovo délky 0, značí se ε) a slova tvaru b(ba)* a aa(ba)* (kde (ba)* je libovolná konečná posloupnost slov ba seřazených za sebou).

Někdy se u nedeterministických automatů povolují navíc tzv. ε-přechody. To jsou přechody, před jejichž provedením automat nečte žádné písmeno.

Vaším úkolem je navrhnout vhodný datový typ pro reprezentaci FA, definovat formát vstupu a implementovat jeho načítání. Dále pak je Vaším úkolem vytvořit funkce pro určení, zda je automat deterministický, pro determinizaci, zúplnění a odstranění ε-kroků, minimalizaci deterministického FA, pro určení, zda je množina akceptovaných slov prázdná, konečná. Popisy algoritmů nalzenete ve výše zmíněném studijním textu. Po dohodě lze množinu implementovaných funkcí omezit.

Odhadovaný počet řešitelů: 3.