Lemma .

Buď přechodový graf, v němž počáteční stav je nedefinován (tj. ). Pak lze rozšířit o množinu přechodů tak, že je počáteční stav přechodového grafu .