Für eine Übersetzung von Programmen in Kripke Strukturen ist es eine wesentliche Erleichterung, ein beschriftetes Programm vorliegen zu haben, bei dem für jede Anweisung des Programms der Einstiegs- und Ausgangspunkt eindeutig beschriftet ist. Die systematische Durchführung einer solchen Beschriftung wird im folgenden beschrieben.
Um sich nicht auf eine bestimmte Programmiersprache zu beschränken, wird die Beschriftungs-Vorschrift für verschiedene Anweisungsarten definiert, was leicht auf weitere Anweisungsarten übertragen und erweitert werden kann.
Ausgehend von einer Anweisung P wird eine beschriftete Anweisung PL folgendermaßen induktiv über die Struktur von P definiert:
Falls Pkeine zusammengesetzte Anweisung ist (P ist beispielsweise eine Zuweisung, eine leere Anweisung, eine Pause- oder eine Synchronisations-Anweisung), dann gilt PL=P
Falls P eine sequentielle Komposition ist, also P = P1 ; P2, dann gilt PL = PL1 ;l'' : PL2
Falls P eine Verzweigung ist, also P = ifbthenP1elseP2endif, dann gilt PL = ifbthenl1 : PL1elsePL2endif
Falls P eine Schleife ist, also P = whilebdoP1endwhile, dann gilt PL = whilebdol1 : PL1endwhile
Mit dieser Vorgehensweise erhält man aus P ein beschriftetes Programm PL, das anschließend als Grundlage für die Modellierung des Programms als Kripke-Struktur dienen kann.