Theoretische Info.

Sprachen

Alphabet

Eine formale Sprache $L \subseteq \Sigma^*$ ist eine Menge an Wörtern eines Alphabets. Alle Sprachen haben ein Alphabet, also eine endliche, nichtleere Menge an Zeichen, welches mit einem großenSigma $\Sigma$ dargestellt wird.

$$\Sigma = \{a, b, n, s, o, w\}$$

Grammatik

Eine Grammatik wird wie folgt beschrieben:

$$G = (N, T, P, S)$$

Sie besteht aus den folgenden Bestandteilen:

1. Einer Menge an Nicht-Terminalen $N$.
2. Einer Menge an Terminalen $T$. Das sind die Zeichen des Alphabets.
3. Einer Menge an Produktionen $P$
4. Und einem Startsymbol $S$.

Beispiel:

Nicht-Terminale N = {S, U} Terminale T = {a, b, n, s, o, w} Produktionen P = {S → aU, U → nUs
| sUn | oUw | wUo | b} Startsymbol S

Nicht-Terminale

Auch bekannt als Variablen, werden durch die Regeln der Produktionen in einem Ableitungsschritt ersetzt.

Produktionen

Eine Produktion besteht jeweils aus einem Produktionskopf (ein Nicht-Terminal), einem Ableitungspfeil und einem Produktionsrumpf. Sie gibt an, durch welche Nicht-Terminale und Terminale der Produktionskopf ersetzt werden kann.

Beispiel: Die folgende Produktion gibt an, dass ein U Nicht-Terminales entweder durch ein aU oder ein b ersetzt werden kann.

$$U → aU | b$$

Note

Strenggenommen ist die Form mit dem Strich | nicht Teil der offiziellen Spezifikation, darf im Abitur jedoch verwendet werden. Richtiger wäre, diese Produktion auf zwei Produktionen aufzuteilen: $U \rightarrow aU \\ U \rightarrow b$

Ableitung

Als Ableitung beschreibt man die schrittweise Bildung eines Wortes aus Terminalzeichen, ausgehend von einem Startsymbol. In jedem Schritt wird eine Produktion angewendet, bis nur noch Terminale überbleiben. Für die obere Grammatik wäre dies eine mögliche Ableitung.

$$S \rightarrow aU \rightarrow asUn \rightarrow aswUon \rightarrow aswbon$$

Ableitungsbaum

Eine Ableitung kann auch als Baum dargestellt werden. Die Wurzel dieses Baumes ist bei diesem das Startsymbol. Inneren Knoten stellen Nicht-Terminale, Blätter die Terminale dar. Hier ist der Ableitungsbaum für die oben gezeigte Ableitung.

Akzeptor

Ein Akzeptor ist ein deterministisch endlicher Automat, welcher entscheidet, ob eine Zeichenkette ein Wort einer Sprache ist. Akzeptoren sind wie folgt definiert:

$$A = (Z, \Sigma, \delta, z_0, F)$$

Die einzelnen Bestandteile sind:

1. Eine Menge an möglichen Zuständen $Z$.
2. Das Alphabet der Sprache: $\Sigma$.
3. Die Übergangsfunktion $\delta: Z \times \Sigma \rightarrow Z$, welche für Paare aus Zustand und Zeichen festlegt, in welchen Folgezustand der Akzeptor übergeht.
4. Der Startzustand $z_0$, ein Element aus $Z$.
5. Eine Menge an Endzuständen $F$ aus $Z$.

Ein Wort wird akzeptiert, wenn ausgehend vom Startzustand $z_0$ schrittweise für jedes Zeichen des Wortes ein Übergang gefunden werden kann und der berechnete Endzustand in $Z$ liegt.

Übergangsfunktionen werden oft als Tabelle dargestellt. Diese Tabelle heißt Übergangstabelle. Diese beinhaltet alle Zustände und ihre Folgezustände. Der Aufbau der Tabelle sieht wie folgt aus:

1. Die Zeilenköpfe beinhalten alle Zustände aus $Z$.
2. Die Spaltenköpfe beinhalten die Symbole des Eingabealphabets.
3. Jede Tabellenzelle beschreibt den Folgezustand $\delta(z, x)$.

Aktueller Zustand	Eingabe a	Eingabe b
$\rightarrow z_0$ (Start)	$z_0$	$z_1$
$*z_1$ (Ende)	$z_1$	$z_0$

Diese Tabelle würde die Wörter aaaba und bbba akzeptieren, aber nicht aabb, weil der Zustand nach dem Wort nicht auf einem Endzustand landet.

Syntaxdiagramm

Mit Syntaxdiagrammen lässt sich die Grammatik einer formalen Sprache grafisch darstellen. Die folgenden Regeln werden angewandt:

• Terminale werden in Ovalen dargestellt.
• Nicht-Terminale werden in Rechtecken dargestellt.

Registermaschine

Leistungskursthema

Die Registermaschine ist nur relevant für den Leistungskurs. Ich fand es nur zu interessant um es nicht mit einzubinden. :’)

Eine Registermaschine besteht aus unendlich vielen Registern $R1, R2, R3, ..., RN$, in welchen natürliche Zahlen gespeichert werden. Die Eingabe wird in die ersten $k$ register gespeichert, während alle anderen Register anfänglich mit $0$ befüllt werden. Zusätzlich die Registermaschine einen Akkumulator, in welchem Operationsergebnisse temporär gespeichert werden. Das Program der Registermaschine besteht aus Instruktionen, wobei eine Instruktion jeweils auf eine Zeile geschrieben wird.

Operanden

Bezeichnung	Operand	Bedeutung
Konstant	#i	Der Operand ist die Zahl i.
Direkte Addressierung	i	Der Operand ist die Zahl im Register i.
Indirekte Addressierung	*i	Der Operand ist die Zahl im Register, dessen Index im Register i steht.

Operationen

Befehl	Beschreibung	Limitationen
LOAD x	Lädt x in der Akkumulator.
STORE x	Speichert den Wert des Akkumulators in x.	x darf keine Konstante sein.
ADD x	Addiert x zum Akkumulator.
SUB x	Subtrahiert x vom Akkumulator.
MUL x	Multipliziert x mit dem Akkumulator.
DIV x	Dividiert den Akkumulator durch x.	x darf nicht 0 sein.
GOTO M	Springt zur Marke M.
JZERO M	Springt zur Marke M.	Der Akkumulator muss 0 haben.
JNZERO M	Springt zur Marke M.	Der Akkumulator darf nicht 0 haben.
END	Beendet das Program.

Beispiel: Fakultät

Hier ist ein einfaches Program zur Berechnung der n-ten Fakultät. n wird im ersten Register eingeladen, das Ergebnis landet im zweiten Register.

Factorial.rasm

START:
    LOAD 1
    STORE 10 ; parameter n für STEP
    GOTO STEP

; Register:
;   10 - Fakultätswert n (n!)
;   11 - Derzeitiger Wert (v)
STEP:
    LOAD 11
    ; Erste iteration, v ist 0
    JZERO INIT

    LOAD 10
    ; Falls n gleich null 0, kopiere v nach reg(2)
    JZERO EXIT

    ; v = n * v
    LOAD 10
    MUL 11
    STORE 11
    ; n = n - 1
    LOAD 10
    SUB #1
    STORE 10

    ; Wiederhole
    GOTO STEP

; v = n
; n = n - 1
INIT:
    LOAD 10
    STORE 11
    SUB #1
    STORE 10
    GOTO STEP

EXIT:
    LOAD 11
    STORE 2
    END