Algoritmus: Problém konečnosti
• Vstup: DKA  M = (Q, S, R, s, F);
• Výstup: ANO, pokud L(M) je konečný   NE, pokud L(M) je nekonečný
• Metoda:
• Nechť k = card(Q)
• if existuje z Î L(M), k £ |z| < 2k then napiš(’NE’)
        else napiš(’ANO’)
Problém konečnosti je pro KA rozhodnutelný
Celkově:
Pozn.: Tento algoritmus je založen na tvrzení:
L(M) je nekonečný Û existuje z: z Î L(M), k £ |z| < 2k
23/26