S, A, F, P, N, L jsou hodnoty z úlohy

• Načtení parametrů daného KA, implementace přechodové funkce v C/C++ např. pomocí dvourozměrného pole S x A
• Pro všechny stavy S:
  1. Pro všechny pozitivní případy P se zjistí konečné stavy, množina PF
  2. Pro všechny negativní případy N se zjistí konečné stavy, množina PN
  3. Provede se průnik množin PF a PN, vznikne množina PFN
  4. Pokud je PFN prázdná a |PF| == F, seřadit prvky v PF vzestupně a vypsat s aktuálním stavem

Možné optimalizace:

• Má smysl pokračovat, pokud |PF| != F ?
• Má smysl pokračovat, pokud prvek z PN je v PF?
• Je k něčemu dobrá informace, že s pravděpodobností xy bude vstupní řetězec délky L-√L obsahovat samé 'a'?

Otázka na rozmyšlenou

• Z hlediska výpočetní techniky: je přístup k paměti přechodové funkce KA rychlejší než k registrům CPU při zjištění, že pro určitý znak a stav je KA zacyklen?

Zajímavosti:

• Žádná z testovacích sad nepokrývá případ, kdy PFN je neprázdná množina.