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