In diesem Abschnitt werden wir einige Grundlagen, die Ihnen aus früheren Semestern bekannt sind, kurz auffrischen, um sicherzustellen, daß wir eine gemeinsame Sprache sprechen.
Ein Algorithmus beschreibt ein Verfahren, um ein Problem oder eine ganze Klasse von Problemen
zu lösen.
Der Begriff Algorithmus beruht auf dem Namen des mittelalterlichen Mathematikers
Abu Ja'far Mohammed ibn Musa al-Khowarizm , der um 825 das mathematische Lehrbuch
Kitab al-jabr w'al-muqabala verfasst hat.
Anforderungen an einen Algorithmus
1. Generation
2. Generation
3. Generation
4. Generation
Ein Symbol oder Zeichen ist eine
elementare Einheit:
Eine Zeichenkette ist eine Folge von Symbolen:
Häufig wird eine Zeichenkette durch '' begrenzt. Die
'' bezeichnet man als Delimiter , die nicht zur
Zeichenkette gehören.
Die Länge einer Zeichenkette ist die Anzahl der Symbole:
Präfix einer Zeichenkette z:
beliebige Anzahl führender Symbole von z:
, e, em, emi, emil
Suffix einer Zeichenkette z:
beliebige Anzahl von Symbolen am Ende von z:
, l, il, mil, emil
Konkatenation k zweier Zeichenketten 
:
= ''em'', 
= ''il'': 
= ''emil''
Ein Alphabet ist eine endliche Menge von
Symbolen.
Eine Sprache 
über einem Alphabet 
:
Menge von Zeichenketten aus Symbolen aus :
Auch die leere Menge { } und 
sind Sprachen!
Beispiel:
Die folgende Menge hat unendlich viele Elemente:
Diese Sprache besteht nur aus endlich vielen Elementen:
E ist eine Menge geordneter Paare:
G1 = (V,E)
Ein Pfad in einem gerichteten Graphen ist eine Folge von
Kanten 
, so daß
:
v ist Vorgänger von w und w ist Nachfolger von v
G = (V, E) ist ein (geordneter, gerichteter) Baum , wenn
Beispiel:
Weitere Begriffe:
Ein endlicher Automat ist ein
Fünftupel
Menge der Endzustände
Da die Zustandsübergangsfunktion 
ein Paar (z,a) auf
genau einen Folgezustand abbildet, sprechen wir auch von einem
endlichen deterministischen Automaten, abgekürzt DEA .
Wenn wir in der Zustandsübergangsfunktion vorsehen, daß für
ein Eingabesymbol a mehr als ein Folgezustand möglich ist, so
sprechen wir von einem nichtdeterministischen endlichen
Automaten NEA .
ist dann eine Abbildung auf Mengen von Zuständen.
Bei einer bestimmten Eingabe wird zufällig einer der möglichen
Folgezustände ausgewählt.
Eine Zeichenkette 
wird akzeptiert, wenn es eine
mögliche
Transitionsfolge vom Startzustand gibt, die in einem Endzustand endet.
Formal ist ein NEA ein Quintupel 
das genauso
wie beim DEA definiert ist,
nur für gilt 
Sei A ein Alphabet. Die regulären Ausdrücke über A (r.A.) sind wie folgt definiert
ist ein r.A und bezeichnet die leere Menge 
ist ein r.A und bezeichnet 
a ist ein regulärer Ausdruck und
bezeichnet die Menge 
reguläre
Ausdrücke,
die für die Sprachen 
stehen
Statt + schreibt man häufig auch | (Alternative ).
Wir legen fest, daß der Operator * eine höhere Priorität
hat als die Konkatenation. Der Operator + (|) hat die niedrigste
Priorität.
Beispiele:
{ , a, b, c, ab, ac, abc, abbccc, ...}
{a, , b, bb, bbb, bbbbbbb, ...}
{abc, aabc, abbc, abbccc, ...}
Eine kontextfreie Grammatik (kfG )
ist ein Viertupel
(V, T, P, S):
V = endliche Menge von Variablen
T = endliche Menge von Terminalsymbolen
P = endliche Menge von Produktionen
S = Startsymbol, S 
V
Eine Produktion definiert eine Ersetzungsregel
und ist ein Paar 
, wobei A eine
Variable, 
ist.
Man beachte, daß 
auch die leere Zeichenkette sein kann!
Häufig schreibt man die Elemente von P in der Form 
.
Definition:
Eine Zeichenkette aus 
ist eine Satzform ,
wenn gilt: 
.
Enthält eine Zeichenkette, die aus S abgeleitet werden kann,
nur Terminalsymbole, so bezeichnen wir sie als Satz .
Definition:
Die von einer Grammatik G erzeugte Sprache ist
Zwei Grammatiken 
sind äquivalent,
wenn gilt 
.
Ableitungen eines Satzes einer kfS lassen sich übersichtlich als Bäume
darstellen. Wie in der Informatik üblich, wachsen diese Bäume von oben
nach unten, Wurzel ist das Startsymbol der Grammatik. Die Knoten sind
mit Variablen und Terminalen markiert. Die Blätter eines
Ableitungsbaumes eines Satzes bestehen nur aus Terminalen.
Wenn A ein innerer Knoten mit den Söhnen 
ist,
so ist
eine Produktion der Grammatik.
Beispiel:
Wenn bei jedem Ableitungsschritt immer die am weitesten links stehende
Variable ersetzt wird, sprechen wir von einer Linksableitung.
Analog wird bei einer Rechtsableitung immer die am weitesten
rechts stehende Variable ersetzt.
Beispiel:
Zustandsübergangsfunktion 
Anfangszustand E -> E + E | E * E | id
Linksableitung:
E -> E + E -> E * E + E -> E + E * E + E ->
^ ^ ^
id + E * E + E -> id + id * E + E ->
^ ^
id + id * id + E -> id + id * id + id
Rechtsableitung:
E -> E + E -> E + E + E -> E + E + id ->
^ ^ ^
E + E * E + id -> E + E * id + id ->
^ ^
E + id * id + id -> id + id * id + id
Mit der Grammatik aus dem letzten Beispiel ist es offenbar möglich,
verschiedene Links- oder Rechtsableitungen für einen Satz
anzugeben:
1: E -> E + E -> E * E + E -> ... -> id * id + id
2: E -> E * E -> E * E + E -> ... -> id * id + id
Zu id * id + id existieren damit zwei verschiedene Ableitungsbäume:
Eine kfG, die mehr als einen Ableitungsbaum für einen Satz erlaubt,
bezeichnen wir als mehrdeutig .
Eine Sprache ist mehrdeutig, wenn alle Grammatiken, die die
Sprache erzeugen, mehrdeutig sind.
Man beachte, daß zu einem gegebenen Ableitungsbaum immer
genau eine Links- bzw. Rechtsableitung existiert.
Definition: (Typ-3-Grammatik)
Eine Grammatik G = (V,T,P,S) ist eine Typ-3-Grammatik, wenn alle
Produktionen von der Form
( 
) sind.
Definition: (Typ-2-Grammatik )
Eine Grammatik G = (V,T,P,S) ist eine Typ-2-Grammatik oder
kontextfreie Grammatik, wenn alle
Produktionen von der Form
sind.
Definition: (Typ-1-Grammatik )
Eine Grammatik G = (V,T,P,S) ist eine Typ-1-Grammatik oder
kontextsensitive Grammatik, wenn alle
Produktionen von der Form
sind.
Durch den Ersetzungsprozeß darf die Zeichenkette also nicht verkürzt
werden.
Definition: (Typ-0-Grammatik )
Eine Grammatik G = (V,T,P,S) ist eine Typ-0-Grammatik, wenn alle
Produktionen von der Form
sind.
Der Erzeugungsprozeß muß mit dem Startsymbol beginnen.
Diese Grammatiken werden auch als
Semi-Thue-Systeme bezeichnet.
Beispiel:
Die folgende Grammatik erzeugt die Sprache 
 |  |
 |  |
 |  |
 |  |
Definition: (Kellerautomat )
Ein Kellerautomat ist ein Siebentupel 
Kelleralphabet
Startzustand
Kelleranfangssymbol
Endzustände
ist nichtdeterministisch
Akzeptierte Sprache eines Kellerautomaten:
Ein 
ist
deterministisch wenn
und alle Kellersymbole 
gilt: wenn 
) nicht leer ist,
dann ist 
für alle 
leer. enthält für alle 
höchstens ein Element.
Wegen (1) besteht keine Wahl zwischen Verarbeitung eines Symbols und
einer -Bewegung.
Wegen (2) gibt es für jedes Tripel aus Zustand, Eingabe und Kellersymbol
keine Wahl zwischen verschiedenen Folgekonfigurationen.
Kellerautomaten gelten als nichtdeterministisch, falls nicht explizit
etwas anderes vereinbart wird!!
Deterministische und nichtdeterministische Kellerautomaten sind
nicht äquivalent!
Die Sprache 
wird zwar von einem nichtdeterministischen KA
erkannt, aber nicht von einem deterministischen.
Prof. Dr. Reinhard Völler