LWsystems bietet Ihnen systemübergreifende IT-Beratung und umfassenden Service in allen Fragen Ihrer IT-Infrastruktur.
Rufen Sie uns einfach an!

05455- 932 132 oder 05403- 55 56

Zusammenfassung

Unterabschnitte

Automaten, Reguläre Ausdrücke und Grammatiken

Endliche Automaten

Ein endlicher Automat ist ein mathematisches Modell eines Systems mit Ein- und Ausgaben. Ein solches System befindet sich immer in einer aus einer endlichen Anzahl möglichen internen Konfigurationen (Zustände).

Hierbei unterscheidet, man zwischen deterministischen und nicht deterministischen Automaten. Der deterministische Automat ist so aufgebaut, daß für jeden Zustand genau festgelegt ist, welcher Zustand ihm bei Einlesen eines Eingabesymbols folgt. Beim nichtdeterministischen Automaten können mehrere mögliche Folgezustände auf einen Zustand existieren.

derministische Automaten

Der deterministische endliche¹ Automat wird formal dargestellt als:

$\begin{displaymath}A = (\Sigma, S, \delta, s_0, F) \end{displaymath}$

Dabei gilt:

$\Sigma$: ist das Eingabealphabet, also die Menge aller gültigen Eingaben
: bezeichnet die Zustandsmenge des Automaten . Diese beschreibt alle gültigen Zustände, die der Automat annehmen kann.
$\delta$: ist die Zustandsüberführungsfunktion des Automaten mit $\delta: S \times \Sigma = S$ . In der Zustandüberfürungsmenge kann für jeden Zustand in Kombination mit jedem Eingabesymbol ein Eintrag definert sein. In der Regel besteht die Menge der Zustandsüberführungen jedoch nur aus einer Teilmenge dieses Kreuzproduktes. $\delta$ muß also nicht für alle Paare $(s,a) \in S \times \Sigma$ definiert sein.
: ist der Startzustand des Automaten. ist in der Zustandsmenge des Automaten enthalten da es auch ein Zustand ist: $s_0 \in S$
: (von Final?) ist die Menge der Endzustände des Automaten, wobei gilt $F \subseteq S$ . Ein Automat kann also beliebig viele Endzustände besitzen. In einigen Fällen kann er sogar so aufgebaut sein, daß alle Zustände gleichzeitig Endzustände sind.

Der Automat heißt Deterministisch, wenn für jeden beliebigen Zustand in Kombination mit jedem Eingabesymbol höchstens ein Folgezustand existiert. Die Klasse der Deterministischen Automaten wird mit $DFA_{\Sigma}$ ² bezeichnet.

Definitionen

Wenn die Zustandsübergangsfunktion $\delta$ ein Paar (s,a) auf genau einem Folgezustand abbildet, spricht man auch von einem deterministischem Automaten (DEA). Es existieren keine Verzweigungen im Automaten. Die Verarbeitung verläuft gradlinig, da für jedem Punkt genau ein Folgezustand definiert ist.

Da der Automat nicht verschiedene Möglichkeiten für den Übergang zu einem Folgezustand überprüfen muß und eventuell an einen früheren Verarbeitungsschritt zurückspringen muß (backtracing) kann ein deterministischer Automat sehr schnell ermitteln ob ein Eingabewort akzeptiert wird oder nicht.

Wörter und Alphabete

Ein endlicher Automat verarbeitet Wörter (endliche Zeichenfolgen), die aus atomaren Symbolen gebildet sind. Der endliche Automat hat nach dem Lesen eines Eingabewortes einen anderen Zustand erreicht. Wenn der Automat eine endliche Menge von erreichbaren Zuständen besitzt, wird er endlicher Automat genannt.

Die Symbole, aus denen die Eingabewörter bestehen können werden als das Alphabet $\Sigma$ bezeichnet. Das allgemeine Alphabet wird in symbolischen Darstellungen definiert durch:

$\begin{displaymath}\Sigma = \{a_1, a_2, ..., a_n\}, n \ge 0\end{displaymath}$

Die Wortbildung erfolgt durch Anneinanderreihung von einzelnen Symbole oder auch einzelner vorher definierter Wörter. Die Menge aller Wörter, die über dem Alphabet gebildet werden können, ist gekennzeichnet als: $\Sigma^{\ast}$ . Hierfür gilt:

Jeder Buchstabe $a \in \Sigma$ ist auch ein Wort über $\Sigma$ , d.h. $a \in \Sigma^{\ast}$ . Jeder Buchstabe ist/kann auch ein Wort sein.
Werden bereits konstruierte Wörter hintereinander geschrieben entsteht ein neues Wort. ( $v,w \in \Sigma^{\ast} \Rightarrow vw \in \Sigma^{\ast}$ )
$\epsilon$ , das leere Wort ist ein Wort über jedem Alpahbet und daher in jedem Alphabet enthalten.

Mit $\Sigma^+$ wird die Menge aller Wörter ohne das leere Wort $\epsilon$ bezeichnet.

Sprache

Eine (formale) Sprache ist eine Untermenge aller Wörter, die aus einem Alpahbet gebildet werden können: $L \subseteq \Sigma^{[\ast]}$ . Diese Sprache heißt regulär falls es einen endlichen Automaten A gibt, der sie akzeptiert. Die Klasse der von endlichen Automaten akzeptierten Sprachen über $\Sigma$ wird mit $DFA_{\Sigma}$ ³ symbolisiert. Die Klasse der Regulären Sprachen über $\Sigma$ wird als $REG_{\Sigma}$ bezeichnet.

Zustände

Ein Automat besitzt zwei Speicher. Der Eingabespeicher enthält das jeweilig eingegebene Wort. Der andere Speicher ist der Zustandsspeicher, der den jeweiligen Zustand des Automaten enthält. Da nur endlich viele Zustände zugelassen werden ist der Automat ein endlicher Automat. Formal wird der endliche Automat mit dem Buchstaben

dargestellt. Jeder Automat besitzt einen definierten Anfangszustand

. Die möglichen Endzustände des Automaten werden durch die Menge

bezeichnet, wobei gilt: $F \subseteq S$ .

Die Zustandsüberführungstabelle zeigt, welchen Zustand ein Automat ausgehend vom Ausgangszustand beim Lesen eines Eingangsbuchstabens annimmt.

	Zustand vorher
$\delta$	$s_{0}$	$s_{1}$	$s_{2}$
1	$s_{1}$	$s_{2}$	$s_{2}$
0	$s_{2}$	$s_{1}$	$s_{2}$

Zustandsübergänge

Der Automat geht in Abhängigkeit von seinem aktuellen Zustand und dem nächsten zu verarbeitenden Symbol in einen neuen Zustand über. Diese Verhaltensweise, das ``Programm'' wird durch die Zustandsüberführungsfunktion $\delta$ festgelegt. Ein Zustandsübergang wird formal ausgedrückt als:

$\begin{displaymath}\delta(s,a) = s'\end{displaymath}$

Dieses besagt, daß der Automat wenn er sich im Zustand

befindet und das Eingabesymbol

liest, in den Zustand

übergeht.

Die Programmanweisungen der Menge $\delta$ stellen dar wie ein Zustandsübergang zu erfolgen hat. Die Zustandsübergangsfunktion oder Programmanweisung läßt sich verallgemeinert und formal dann darstellen als:

$\begin{displaymath}\delta = \{(s,a,s')\vert\delta(s,a)=s'\}\end{displaymath}$

Der Automat befindet sich im Zustand s und liest das Eingabesymbol a. Gemäß der Zustandsüberführungsfunktion $\delta$ geht er jetzt in den Zustand s' über. Das Tripel

ist also eine Programmzeile des Programms.

Konfigurationsübergänge

Eine Konfiguration

beschreibt den aktuellen Stand der Verarbeitung eines Wortes durch den Automaten (

). Der Konfigurationsübergang wird zum einen festgelegt durch den aktuellen Zustand des Automaten

, zum anderen durch das noch zu verarbeitende Suffix des Eingabewortes

Die Konfiguration beschreibt also einen Zustand beliebigen Zustand während des Programmlaufs.

Ein Übergang von einer Konfiguration ⁴ zu einer anderen kann stattfinden, falls der Zustandsübergang $\delta(s,a) = s'$ existiert. Für den Konfigurationsübergang muß also ein passender Zustandsübergang vom alten in den neuen Zustand definiert sein. Formal wird der Konfigurationsübergang wie folgt ausgedrückt:

$\begin{displaymath}(s,w) \vdash (s',w')\end{displaymath}$

nichtdeterministische Automaten

Bei den Nichtdeterministischen Automaten ist die Zustandüberführung als Relation aufgebaut. Das heißt, daß für jeden Zustand in Verbindung mit jedem gelesenen Eingabesymbol mehrere Folgezustände existieren können. Beim Abarbeiten eines Eingabewortes muß ein Automat dieser Klasse daher an ``Verzweigungen'' mit Hilfe von Trial-And-Error überprüfen, ob ein Zustandsübergang letztendlich zu einem Endzustand führt. Falls dieser Zustandübergang nach einigen Schritten dazu führt, daß für eine Kombination aus Eingabesymbol und aktuellem Zustand kein Folgezustand definiert ist, muß der Automat wieder an die letzte Zustandsüberführung zurückspringen, an der mehrere Möglichkeiten des weiteren Vorgehens bestanden. Mit steigender Zahl von möglichen Zustandüberführungen steigt die Laufzeit dieses Automaten bei Überprüfung eines Wortes exponentiell an. Die Klasse der nichtdeterministischen Automaten wird mit $NFA_{\Sigma}$ ⁵ symbolisiert.

Äquivalenz deterministischer und nichtdeterministischer Automaten

Zu jedem nichtdeterministischen Automaten läßt sich ein äquivalenter deterministischer Automat definieren, der genau dieselbe Sprache akzeptiert. Die Überführung eines nichtdeterministischen Automaten in den äquivalenten deterministischen kann mit Hilfe der Potenzmengenkonstruktion durchgeführt werden. Die Grundidee dieser Überführung ist, daß die nichtdeterministischen parallelen Übergänge zu einer Berechnung und somit zu einem Übergang zusammengefaßt werden. Die Zustände bestehen dann aus Mengen von Zuständen. Die Menge aller möglichen Zustände des deterministischen Automaten ist die Menge aller Teilmengen von S, der Zustandsmenge.

Aufgrund dieser Äquivalenz der beiden Klassen von Automaten akzeptiern beide auch dieselbe Klasse von Sprachen, die Klasse der regulären Sprachen.

Epsilonautomaten

Der $\epsilon$ - Automat ist ein Automat, in dessen Zustandsüberführungsrelation auch $\epsilon$ -Übergänge vorkommen dürfen. Der $\epsilon$ -Übergang ist dadurch gekennzeichnet, daß der Automat von einem Zustand in einen anderen wechselt, ohne daß dabei ein Eingabesymbol gelesen wurde. Der Lesekopf bleibt beim $\epsilon$ -Übergang also stehen.

Ein nichtdeterministischer Automat ist genau betrachtet ein $\epsilon$ -Automat, bei dem die $\epsilon$ -Übergänge fehlen. Daher ist die Klasse der Nichtdeterministischen Automaten eine Untermenge der $\epsilon$ -Automaten. Daher läßt sich jeder $\epsilon$ -Automat in einen Nichtdeterministischen transformieren. Gerade bei der modularen Zusammensetzung von endlichen Automaten sind die $\epsilon$ -Übergänge sehr hilfreich. Hiermit lassen sich die einzelnen Automatenmodule, die ja jeder für sich abgeschlossene Automten sind, einfach miteinander verbinden. Beim Übergang vom einen Automaten in den anderen wird hier einfach ein $\epsilon$ -Übergang durchgeführt. Mit Hilfe dieser Möglichkeiten lassen sich daher Sprachen miteinander verknüpfen.

Verallgemeinerte Automaten

Zur Vereinfachung von Automaten mit einer Folge von deterministischen Übergängen können die verallgemeinerten Automaten genutzt werden. Hier wird der Automat dahingehend erweitert, daß er für einen Konfigurationsübergang anstatt eines Symbols ein komplettes Wort akzeptiert. Mit den verallgemeinerten Automaten läßt sich eine vereinfachte Darstellung eines Automaten realisieren, da hier ein Teil der Konfigurationsübergänge zu jeweils einem einzigen zusammengefaßt wurde. Es läßt sich ein Beweis führen, daß für jeden verallgemeinerten Automaten ein äquivalenter endlicher Automat existiert. Ein verallgemeinerter endlicher Automat wird mit $GFA_{\Sigma}$ ⁶ bezeichnet.

Zusammenfassung

Endliche Automaten modellieren ein Black-Box-Modell. In Abhängigkeit ihres aktuellen Zustands und einer Eingabe gehen sie gemäßeiner festgelegten Zustandsüberführung in einen neuen Zustand über. Die Abarbeitung eines Eingabewortes, einer endlichen Folge von Eingabesymbolen, geschieht durch einen Prozeß, der durch eine Folge von Konfigurationsübergängen formal beschrieben werden kann. Ist der Automat nach vollständiger Abarbeitung des Eingabewortes in einem Endzustand, dann akzeptiert der Automat dieses Wort. Kann er ein Eingabewort nicht komplett abarbeiten oder ist nach seiner Abarbeitung nicht in einem Endzustand, akzeptiert er das Wort nicht. Die Menge aller von einem endlichen Automaten aktzeptierten Wörter stellt die von ihm akzeptierte Sprache dar. Von endlichen Automaten akzeptierte Sprachen heißen reguläre Sprachen. Jeder endliche Automat kann in einen Automaten einer anderen Klasse transformiert werden:

$\begin{displaymath}REG_{\Sigma} = DFA_{\Sigma} = NFA_{\Sigma} = \epsilon FA_{\Sigma} = GFA_{\Sigma}\end{displaymath}$

Minimierung endlicher Automaten

Zu jedem endlichen Automaten läßt sich ein äquivalenter minimaler Automat mit der mindestmöglichen Zahl von Zuständen konstruieren. Zwei minimalisierte Automaten unterscheiden sich höchstens in der Bezeichnung ihrer Zustände voneinander. Alle anderen Parameter wie

Eingabesymbole
Anzahl der Zustände
Anzahl der Endzustände
Zustandsüberführungen

sind gleich. In diesem Falle besteht eine Strukturgleichheit zwischen den Automaten. In diesem Falle werden die Automaten auch isomorph zueinander genannt.

Ermittlung des minimalen Automaten

Die Minimierung eines Automaten erfolgt durch die Zusammenfassung der Zustandsübergänge, die für ein Eingabesymbol (Zeile in der Zustandsübergangstabelle) einen gemeinsamen Zielzustand erreichen. Hierzu werden die einzelnen Zustandsübergänge blockweise zusammengefaßt.

Die Zustandstafel wird zunächst in zwei große Blöcke aufgeteilt, wobei ein Block möglichst derart zusammengefaßt werden sollte, daß die Folgezustände für ein Eingabesymbol einen gemeinsamen Zielzustand(-sblock) anzeigen.
Falls in dieser Aufteilung die Zielzustände eines Blocks für ein Eingabesymbol (Zeile) noch keinen gemeinsamen Zielblock erreicht haben, muß einen erneute Blockaufspaltung erfolgen. Hierbei dürfen auch Spalten zusammengefaßt werden, die nicht direkt nebeneinander liegen.

Der minimale Automat ist erreicht, wenn alle Zielzustände für einen Block auf einen gemeinsamen Zielblock verweisen. Das Zustandsdiagramm des so entstandenen Automaten wird erzeugt, indem die Blöcke jeweils einen Zustand darstellen und die Zielzustände als Verweise auf die jeweiligen Zielblöcke eingezeichnet werden. (s.a. 19)

Reguläre Ausdrücke

Eine reguläre Sprache kann definiert werden, indem ein endlicher Automat konstruiert wird, der diese Sprache akzeptiert. Neben dieser akzeptierenden Definition kann die Sprache auch auf beschreibende Art und Weise definiert werden. Hierbei wird festgelegt, aus welchen Symbolen die Sprache zusammengesetzt ist und wie diese miteinander verknüpft werden dürfen. Die Definition der Sprache erfolgt mit Hilfe der regulären Ausdrücke.

Ein regulärer Ausdruck, der über einem Alphabet $\Sigma$ gebildet wird definiert im Prinzip eine Menge von Wörtern, die sich durch die Anwendung dieses Ausdrucks ergeben. Der Ausdruck definiert somit die Sprache über dem Alphabet $\Sigma$ . Wenn für $\alpha$ gilt: $\alpha \in REXP_\Sigma$ ist $L(\alpha)$ die von $\alpha$ definierte Sprache.

Reguläre Ausdrücke und Sprachen

Die Interpretation des reglulären Ausdrucks zur Erzeugung der Sprache geschieht nach festgelegten Vorschriften, den (Interpretations-)Vorschriften :

$L(\Lambda)=\emptyset$: $\Lambda$ definiert die leere Sprache. Der reguläre Ausdruck $\Lambda$ entspricht der leeren Sprache mit dem Symbol $\emptyset$ . Im regulären Ausdruck bedeutet dieses das ``nichts'' (wie in 'kein- oder mehrmals'). Die leere Sprache ist eine Sprache, die eigentlich nicht existiert, sie enthält nicht einmal das leere Wort $\epsilon$ .
Die $\emptyset$ verhält sich bei dem $\vert$ -Operator wie die 0 bei der Addition.
$L(E)=\{\epsilon\}$: legt die Sprache fest, die nur das leere Wort enthält. Der reguläre Ausdruck ist der Einsoperator. Er steht für die Sprache, die nur das leere Wort $\epsilon$ enthält.
$\epsilon$ verhält sich bezüglich des $\circ$ -Operators wie die 1 bei der Multiplikation.
$L(a)=\{a\}$: für alle $a \in \Sigma$ : jeder Buchstabe aus $\Sigma$ beschreibt jeweils die Sprache, die nur ihn selbst als einziges Wort enthält.

Wie oben beschrieben können Sprachen beliebig miteinander verknüpft werden. Somit können die regulären Ausdrücke zur Erzeugung der Sprachen gleichfalls mit den Mengenoperationen verknüpft werden. Für diese Operationen lassen sich die folgenden Aussagen treffen.

Sind $\alpha, \beta \in REXP_\Sigma$ , dann gilt:

$L(\alpha \bullet \beta) = L(\alpha) \circ L(\beta)$: : Die Konketantion regulärer Ausdrücke ist die Konketanation der durch sie definierten Sprachen.
$L(\alpha \Vert \beta) = L(\alpha) \cup L(\beta)$: : Die Selektion (ODER- Auswahl) reguläerer Ausdrücke ist die Vereinigung der durch sie definierten Sprachen.
$L(\alpha^\otimes) = (L(\alpha))^*)$: : Der Wiederholungsparameter wird durch das Kleene-Stern-Produkt ⁷ interpretiert.

Der $\vert$ - Operator (Selektions bzw. ODER Operator) weist die Besonderheit auf, daß für Ihn die Idempotenz gilt. Das heißt daß für jeden regulären Ausdruck gilt:

$\begin{displaymath}(\alpha \vert \alpha) \equiv \alpha\end{displaymath}$

denn

$\begin{eqnarray*} L(\alpha \vert \alpha) &=& L(\alpha) \cup L(\alpha)\\ &=& L(\alpha) \end{eqnarray*}$

Bei Zahlen $\ne 0$ gilt diese nicht.

Anwendung regulärer Ausdrücke

Reguläre Ausdrücke werden in der Softwaretechnik zur Beschreibung der Syntax von Eingabefeldern in Dialogmasken und Formularen benutzt. Die Software, die die Richtigkeit der Eingabe überprüft, kann mit Hilfe von Scanner-Generatoren automatisiert erzeugt werden. Hier müssen nur noch die Regulären Ausdrücke erstellt werden, die dann in Quellcode der Programmiersprache (i.d.R. C) umgesetzt werden.

Die von dem Generator erzeugten Prozeduren werden auch Scanner oder Lexical Analyzer genannt. Ein bekannter Scanner-Generatore ist z.B. (f)lex unter Unix.

Grammatiken

Neben den akzeptierenden und beschreibenden Konzepten für Sprachen, wie sie mit Hilfe von Automaten und regulären Ausdrücken erfolgen (s.a. 4), ist noch das Konzept der Spracherzeugung mittels Grammtiken möglich. Eine Grammatik definiert Regeln (Produktionen), die angeben wie die Worte einer Sprache gebildet werden:

Satz $\longrightarrow$ Subjekt Prädikat Objekt
Subjekt $\longrightarrow$ Artikel Substantiv
Artikel $\longrightarrow$ der | die | das
Substantiv $\longrightarrow$ Junge | Mädchen | Kind | Hund
Prädikat $\longrightarrow$ Verb
Verb $\longrightarrow$ bellt | bellen | beißt | jagt | sucht
Objekt $\longrightarrow$ Artikel1 Substantiv
Artikel1 $\longrightarrow$ den | die | das

Die Symbole links vom $\longrightarrow$ werden als Variablen bezeichnet, die durch die rechten Seiten der Produktionen ersetzt werden können. Zeichenketten aus Kleinbuchstaben sind Terminale, die nicht weiter ersetzt werden können. Alternativen werden durch senkrechte Striche | getrennt. Eine Variable (Satz) ist ausgezeichnet, bei ihr beginnt der Ersetzungsprozeß. Jetzt können beliebige Sätze aus den Worten gebildet werden, indem die Regeln angewandt werden, bis keine Variablen mehr vorhanden sind. Mit diesen Regeln können allerdings auch Sätze gebildet werden wie:
Die Junge bellt das Mädchen

Der Satz ist syntaktisch korrekt, also aus dem Startsymbol durch die Ableitung der Grammatikregeln hergeleitet. Allerdings ist die Bedeutung, die SemantikSemantik eher zweifelhaft. Diese Situation gleicht der bei einer Programmiersprache, wenn einer INT-Variablen z.B. ein FLOAT-Wert zugewiesen werden soll. Die Konstruktion ist nach den den Regeln der Grammatik korrekt.

Neben den semantischen Problemen besteht bei Grammatiken das Problem der Eindeutigkeit.

Typ-3-Grammatiken

Typ-3-Grammatiken erzeugen Wörter indem sie ausgehend von einem Startsymbol mit Hilfe von Ersetzungsregeln die einzelnen Buchstaben durch Symbolersetzung erzeugen. Typ-3-Grammatiken sind untereinander äquivalente erzeugende Konzepte für reguläre Sprachen, äquivalent zu endlichen Automaten und regulären Ausdrücken. Mit einer Typ-3-Grammatik kann eine reguläre Sprache erzeugt werden. Eine nicht reguläre Sprache kann hiermit nicht erzeugt werden. Das heißt, daß z.B. bei der Erzeugung nicht kontrolliert werden kann ob bei einem Wort die Anzahl der a's und b's gleich ist.

Typ-3-Grammatiken hinsichtlich der Erzeugung bzw. überprüfung einer Sprache den endlichen Automaten oder den Regulären Ausdrücken äquivalent. Die Nonterminale einer Grammatik können auch als Zustände bezeichnet werden. Man merkt sich mit einem Nonterminal den aktuellen Erzeugungszustand des abzuleitenden Wortes, von dem aus in einem ``Zustandsübergang'' ein neues Symbol erzeugt wird. Ein Automat, der zu dieser Grammatik äquivalent ist, wird in diesem Falle das Symbol akzeptiert.

Die allgemeine Typ-3-Grammatik ist wie folgt aufgebaut:

$\begin{eqnarray*} G & = & (\Sigma, N, P, S)\\ mit: & &\\ \Sigma &: & Termin... ...\ P &: & Produktions- oder Regelmenge\\ S &: & Startsymbol \end{eqnarray*}$

Anwendung der Grammatik

Die Erzeugung eines Wortes mit Hilfe der Typ3-Grammatik erfolgt, indem die in der Regelmenge

definierten Regeln ausgehend vom Startsymbol angewandt werden. Diesen Vorgang bezeichnet man auch als Ableitung der Grammatik. Er wird solange durchgeführt, bis das abgeleitete Wort jeweils kein Nonterminalsymbol (

)⁸ mehr enthält. Pro Ersetzungsvorgang kann nur ein Nonterminal durch ein Terminalsymbol ersetzt werden.

Beispiel (s.a. )
Die folgende Typ3-Grammatik soll abgeleitet werden:

$\begin{eqnarray*} G &=& (\{0,1\}, \{S,A,B\}, P, S)\\ \\ mit:&&\\ P &=\{ & ... ... A \rightarrow 0A, A \rightarrow 1A, A \rightarrow \epsilon\}\\ \end{eqnarray*}$

S wird ersetzt durch , oder
A wird ersetzt durch , oder nichts $\epsilon$ . Bei Ersetzung mit $\epsilon$ endet die Ableitung, da kein Nonterminalsymbol mehr vorhanden ist.

Im obigen Falle werden Wörter erzeugt, in denen als Infix vorkommt. Die Ersetzung $S \rightarrow 0S$ bzw. $S \rightarrow 1S$ können beliebig lange kombinationen erzeugen. Es ist auf jeden Fall garantiert, daß irgendwann die Ersetzung durchlaufen wird und somit die Kombination in dem Wort vorkommt.

Die Typ-3-Grammatiken lassen sich in rechtslineare und rechtslineare Grammatiken sowie ihre verallgemeinerten Varianten unterteilen. Die rechtslinearen Grammatiken erzeugen ein Wort buchstabenweise von links nach rechts. Hier ist jede Ableitungsregel so aufgebaut, daß in jedem Ableitunsschritt rechts am schon bestehenden Wort ein neuer Buchstabe angehängt wird. Bei den linkslinearen Grammatiken ist dieses umgekehrt.

Die verallgemeinerten Typ-3-Grammatiken sind so aufgebaut, daß hier in jedem Ableitungsschritt nicht nur ein Terminalbuchstabe, sondern sofort ein ganzes Terminalwort erzeugt wird.

Mit einer Typ-3-Grammatik läßt sich eine Sprache der Form $L = \{L = a^nb^n \vert n \ge 0\}$ nicht ableiten, da diese Sprache nicht regulär ist.

Eigenschaften Regulärer Sprachen

Die Konzepte zur Beschreibung regulärer Sprachen sind:

akzeptierende Konzepte: endliche Automaten, nichtdeterministische endliche Automaten, Automaten mit $\epsilon$ -Übergängen, verallgemeinerte endliche Automaten
Die Sprache ist eine reguläre Sprache, wenn sie von einem (endlichen) Automaten akzeptiert wird.
beschreibendes Konzept: reguläre Ausdrücke;
Die reguläre Sprache wird durch einen regulären Ausdruck beschrieben. Dieser legt sozusagen den Aufbau der einzelnen Wörter fest.
erzeugende Konzepte: Typ-3-Grammatiken (rechtlineare, linkslineare, verallgemeinerte rechtslineare,verallgemeinerte linkslineare Grammatiken)
Die Typ-3-Grammatik gibt Regeln an, mit denen aus einem Startwert alle Wörter einer Sprache hergestellt werden können.

Abschlußeigenschaften

Die Klasse $REG_{\Sigma}$ der regulären Sprachen über einem Alphabet ist abgeschlossen gegenüber allen gängigen Operationen. Das bedeutet, daß die Verknüpfung von zwei Sprachen mit Hilfe dieser Operationen als Ergebnis wieder eine reguläre Sprache ergibt.

Die hier gängigen Operationen auf die regulären Sprachen sind:

Die Vereinigung von zwei regulären Sprachen ( $L_1 \cup L_2 \in REG_{\Sigma}$ ),
Die Differenz zweier regulärer Sprachen ( $L_1 - L_2 \in REG_{\Sigma}$ ),
Das Komplement einer regulären Sprache ist wieder regulär ( $\Sigma^* - L \in REG_{\Sigma}$ ),
Der Durchschnitt regulärer Sprachen ist wieder regulär ( $L_1 \cap L_2 \in REG_{\Sigma}$ ),
Die Konkatenation regulärer Sprachen ist regulär ( $L_1 \circ L_2 \in REG_{\Sigma}$ ),
das Kleene-Stern-Produkt einer regulären Sprache ist regulär ( $L^* \in REG_{\Sigma}$ )⁹ interpretiert.,
Die Spiegelung einer regulären Sprache ist regulär ( $SP(L) \in REG_{\Sigma}$ ).

Das Pumping-Lemma für reguläre Sprachen

Die Frage, ob eine Sprache regulär ist, ob sie also durch einen regulären Ausdruck beschrieben, bzw. durch einenn endlichen Automaten erkannt werden kann, kann man mit Hilfe des Pumping-Lemmas beantworten¹⁰. Das Pumping-Lemma gibt eine notwendige Eigenschaft für reguläre Sprachen an. Das heißt jede reguläre Sprache muß das Pumping-Lemma erfüllen. Allerdings ist diese Eigenschaft nicht hinreichend, d.h. es gibt Sprachen die nicht regulär sind aber das Pumping-Lemma erfüllen.

Entscheidbarkeitsprobleme

In der Praxis des Compilerbaus ist ein Entscheidbarkeitsproblem von großer Bedeutung: das Wortproblem. Ein Quellcodeprogramm stellt ein Wort über einer Sprache, der Programmiersprache dar. Der Compiler muß entscheiden, ob dieses Programm ein gültiges Wort zu dem vorgegebenen Alphabet, daß alle möglichen syntaktisch gültigen Programme dieser Programmiersprache darstellt. Neben dem Wortproblem sind in der Praxis noch anderen Entscheidbarkeitsprobleme relevant. Für alle diese Probleme wurden passende Algorithmen entwickelt.

das Wortproblem ( $w \in L$ ),
das Leerheitsproblem ( $L = \emptyset$ ),
das Endlichkeitsproblem ( $\vert L\vert < \infty$ ),
das Durchschnittsproblem ( $L_1 \cap L_2 = \emptyset$ ),
das Äquivalenzproblem ().

Nichtreguläre Sprachen und Grenzen endlicher Automaten

Eine reguläre Sprache wird dadurch definiert, daß es einen endlichen Automaten gibt, der sie akzeptiert. Dieser Automat ist durch seinen endlichen Speicher begrenzt, der ihm nur eine endliche Menge von Zuständen erlaubt. Eine nichtreguläre Sprache ist dadurch gekennzeichnet, daß sie von keinem regulären Automaten akzeptiert wird.

Eine sehr einfache Sprache, die dieser Bedingung genügt ist die Sprache:

$\begin{displaymath}L = \{a^kb^k \vert k \ge 0 \}\end{displaymath}$

Diese Sprache muß hat u.a. die Eigenschaft, daß der hintere Teil ihrer Wörter im Aufbau vom vorderen Teil abhängt. Für diese Sprache läßt sich zeigen, daß sie das Pumping-Lemma nicht erfüllt, sie somit nicht regulär sein kann, da das Erfüllen des Pumping-Lemma eine notwendige Eigenschaft ist.

In Programmiersprachen sind geschachtelte Blockstrukturen möglich. Diese lassen sich auf die Form $L = \{a^kb^k \vert k \ge 0 \}$ verallgemeinern. Eine Sprache dieser Form ist aber nicht regulär, so daß Programmiersprachen nicht mit Typ-3-Grammatiken erzeugt werden können bzw. durch Compiler in Form von endlichen Automaten verarbeitet werden können.

Endliche Maschinen

Ein Automat besizt keine Ausgabefunktion. Der akutelle Zustand oder ein Ergebnis kann also nicht sichbar gemacht werden. Wenn ein Automat, mit einer Ausgabefunktion versehen wird, bezeichnet man ihn als Maschine. Genau wie bei den möglichen Eingaben wird die Menge der Möglichen Ausgaben in einem Alphabet zusammengefaßt. Wir sprechen dann vom Ausgabealphabet $\Delta$ . Eine Maschine ist also definiert durch:

$\begin{eqnarray*} M &=& (\Sigma, \Delta, S, \delta, \lambda, s_0)\\ mit&&\\ ... ...ktion\\ \lambda&:& Ausgabefunktion\\ s_0 &:& Startzustand\\ \end{eqnarray*}$

Maschinentypen

Mealy- Maschinen

Die Mealy-Maschine ist dadurch gekennzeichnet, daß die Ausgabe den Zustandsübergängen zugeordnet ist. Damit hängt die Ausgabe der Mealymaschine vom jeweiligen Eingabesymbol und vom aktuellen Zustand ab. Da die Ausgabe mit jedem Zustandsübergang erfolgt, sind die Ein- und Ausgabewörter bei der Mealy-Maschine immer gleich lang. Nach dem Einschalten liegt bei dieser Maschine noch keine Ausgabe vor, da sie sich im Startzustand befindet und noch kein Zustandsübergang stattgefunden hat.

Simulation von Mealy- Maschinen durch Automaten

Ein endlicher Automat ist im gewissen Sinne äquivalent zu einer Mealy-Maschine. Zu einer Mealy-Maschine läßt sich immer ein Automat entwickeln, der als Eingabewort die Kombination von Eingabe und Ausgabe der Mealy-Maschine akzeptiert.

Moore-Maschinen

Die Mealy-Maschine besitzt den Nachteil, daß sie bei Einschalten noch keine Ausgabe erzeugt, da sie sich im Startzustand befindet und noch kein Konfigurationsübergang stattgefunden hat. Um diesen Mangel zu beheben muß den Startzustand eine Ausgabe zugeordnet werden. Diese Vorgehensweise wird bei der Moore-Maschine angewandt. Hier ist die Ausgabe nur vom jeweiligen Zustand abhängig. Das Ausgabewort der Moore-Maschine ist immer um ein Symbol länger als das Eingabewort, da hier schon beim Einschalten eine Ausgabe erfolgt.

Eine Mealy-Maschine läßt sich in eine Moore-Maschine tranformieren und umgekehrt. Bei Umwandlung in die Moore-Maschine muß beachtet werden, daß eventuell neue Zustände (Zustandssplitting) eingeführt werden. Diese erzeugen je nach vorhergehenden Eingabesymbol eine andere Ausgabe. Bei der Mealy-Maschine erfolgt dieses systembedingt automatisch.

Äquivalenz

Die Mealy- und die Moore-Maschine sind nur in eingeschränktem Maße äquivalent zueinander. Aufgrund der unterschiedlichen Länge der Ausgabewörter ist eine Äquivalenz im engeren Sinne nicht gegeben. Falls die erste Ausgabe der Moore-Maschine nicht berücksichtigt wird, lassen sich die beiden Typen ineinander umwandeln. Hieraus läßt sich folgern, daß alle Mealy- berechenbaren Probleme auch Moore-berechenbar sind und umgekehrt.

Praktische Anwendungen

Endliche Maschinen finden praktische Anwendungen z.B. bei der Lösung von Multiplikationen, Additionen von natürlichen und von Dualzahlen, Paritätsbitergängzung und -prüfung sowie Teilbarkeitsteste oder den Eintrittsautomaten.

Zellulare Automaten

Automaten werden auch zur Modellierung von vernetzten Systemen eingesetzt, wie dieses z.B. in den Zellstrukturen des Gehirns oder anderen Nervenzellen zu finden ist. Der Zustand einer einzelnen Zelle hängt von den Zuständen ihrer direkten Nachbarzellen ab. Bei der Modellierung dieser Systeme wird jede einzelne Zelle als Automat dargestellt, dessen Zustandsänderung abhängig von den Nachbarzellen ist. Ein Eingabewort wird also aus den Zuständen der Nachbarzellen gebildet. In festgelegten Takten finden die Zustandsänderungen der Zellen synchron statt. Die Untersuchungen an diesem System finden in der Regeln an n-dimensionalen Gittern statt. Hierfür wird für die einzelne Zelle der sogenannte Nachbarschaftsindex aufgestellt, der in allgemeiner Beschreibung die Koordinaten der Nachbarzellen enthält, die für die Auswertung des Konfigurationsübergangs berücksichtigt werden müssen. Mit entsprechenden Algorithmen lassen sich dann Fragen untersuchen wie

Treten Wiederholungen von Mustern und Teilmustern (nach welcher Anzahl von Perioden) auf?
Wann wird die Konfigurationsfolge stationär?
Können sich zellulare Automaten mit unterschiedlichen Nachbarschaftsindexen (unterschiedliche Dimensionen) gegenseitig simulieren?
Welche Sprachklassen lassen sich mit einem zellularen Automaten simulieren?
Welche Funktionenklassen können mit welchen Typen von zellularen Automaten berechnet werden, wenn die Automaten mit Ein- und Ausgabe versehen werden?

Die Konzepte zellularer Automaten werden in der Biologie bei der Beschreibung und Untersuchung von Zellwachstum oder Populationsmodellierung, in der Physik zur Analyse von Kristallwachstum und in der Informatik bei Entwicklung von Parallelrechnern eingesetzt.

Ein spezielles Problem ist das Firing-Squad-Synchronization-Problem . Im allgemein Fall wird hier untersucht, wie eine Reihe von Automaten, bei denen Nachrichten zum jeweiligen Nachbarn übermittelt werden können, so gesteuert werden können, daß alle Automaten nach einiger Zeit (=Anzahl von Takten) synchron den gleichen Zustand erreichen.

Petri-Netze

Die Petri-Netze dienen zur Simulation von miteinander kommunizierenden asynchron laufenden Prozessen. Ein einfaches Beispiel ist der konkurrierende Zugriff auf ein Peripheriegerät in einem Rechner mit mehreren Prozessoren.

Zum Aufbau eines Petri-Netzes wird zuerst die statische Sicht auf das System modelliert. Hier sind alle Systemzustände enthalten. Die ``Laufrichtung'' der Transitionen (Prozesse) wird durch Pfeile markiert werden. Zudem werden die Punkte miteinander verbunden, an denen die Prozesse miteinander kommunizieren können (sog. Semaphore ). Die Kommunikation erfolgt an diesen Stellen mit Hilfe eines Tokens, welches von den Prozessen belegt, d.h. ``mitgenommen'' werden kann. Dieses entspricht dem Setzen eines Flags. Eine Regel bei der Modellierung ist, daß eine Transition nur feuern kann, wenn alle vorhergehenden Zustände mit mindestens einem Token belegt sind. Der jeweilige Prozeß nimmt das gemeinsame Token mit und signaliert hiermit die Belegung der Ressource.

Die Untersuchung dieses Systems im asynchron laufenden Zustand kann darüber Auskunft geben, ob das Gesamtsystem in einen Zustand laufen kann, der eine Problemlösung von außen erfordert. Beispiele für solche Zustände sind:

Konfliktsituation: Da zwei Prozesse gleichzeitig das gleiche dürfen tritt eine Pattsituation auf. Diese muß von außen gelöst werden, indem bestimmt wird wer zuerst weiterlaufen soll.
Verklemmung: Zwei Prozesse warten kreuzweise auf ein Ergebnis des jeweils anderen Prozesses.
tote Transition: Hier werden Zustände im System gefunden, die ein ``Hängen'' eines einzelnen Prozesses feststellen können. Ein solcher Zustand kann z.B. durch eine unglückliche Modellierung des Systems auftreten, indem auf einen Zustand gewartet wird der nie eintreten kann.

Die Anwendungsgebiete von Petri-Netzen liegen in der Systemanalyse und im Entwurf. Softwarewerkzeuge (sog. CASE-Tools) können Analyse und Entwurf von Petri-Netzen unterstützen. Ein weiteres Anwendungsgebiet ist die Konzeption und Realisierung von Workflow-Managementsystemen.

Kontextfreie Grammatiken

Wie oben (3.1) gezeigt, kann eine Sprache der Form $L = \{a^nb^n\vert n \ge0\}$ mit Hilfe einer Typ-3-Grammtik nicht erzeugt werden. Um diese Sprache zu erzeugen müssen gleichzeitig zwei Terminalsymbole¹¹ so parallel erzeugt werden¹², daß im nächsten Schritt wieder zwei Terminalsymbole parallel erzeugt werden können. Die Typ-3-Grammatik läßt höchstens die Erzeugung von einem Terminalsymbol pro Ersetzungsvorgang zu. Mit der Erweiterung der Möglichkeiten auf die Erzeugung von mehreren terminalen Symbolen pro Ersetzungsschritt ist eine solche Sprache definierbar.

Die Klasse der regulären Grammatiken (Typ-3-Grammatiken) ist eine Obermenge der Klasse der kontextfreien Grammatiken. Falls das Eingabealphabet $\Sigma$ mehr als ein Symbol erhält ist die Klasse der kontextfreien Grammatiken eine echte Untermenge der regulären Grammatiken. Die kontextfreien Grammatiken zählen zu den Typ-2-Grammatiken.

Eine kontextfreie Grammatik (kfG) ist ein Viertupel:
(V,T,P,S)
mit:

V =	endliche Menge von Variablen
T =	endliche Menge von Terminalsymbolen
P =	endliche Menge von Produktionen
S =	Startsymbol, $S \in V$

Eine Produktion definiert eine Ersetzungsregel und ist ein Paar (A, $\alpha$ ), wobei A eine Variable, $a \in (V \cup T))^*$ ist. $\alpha$ kann auch die leere Zeichenkette sein. Die Elemente der Produktionen werden häufig als $A \longrightarrow \alpha$ beschrieben.

Da auf der linken Seite einer Produktion nur eine einzelne Variable stehen darf, kann diese Variable unabhängig vom Kontext ersetzt werden - daher die Bezeichnung kontextfreie Grammatik.

Die Klasse der kontextfreien Grammatiken haben für die Definition von Programmiersprachen eine sehr große Bedeutung. Diese Sprachen können durch kontextfreie Grammatiken mit Hilfe eines Formalismus beschrieben werden, der es erlaubt aus den Sprachbeschreibungen in vielen Fällen automatisch Parser zu generieren, die überprüfen können ob ein Wort zur Sprache gehört. Wenn dieses so ist, ist das Programm syntaktisch korrekt.

Vereinfachung kontextfreier Grammatiken

Die kontextfreien Grammatiken lassen sich mittels dreier Verfahren vereinfachen.

Eliminierung von $\epsilon$ - Regeln, so daß die Grammatiken $\epsilon$ - frei werden. Hierbei werden einige Regeln so zusammengefaßt, daß sie schon enden bevor sie auf ein $\epsilon$ - Symbol treffen.
Eliminierung nutzloser Symbole, die für die Erzeugung von terminalen Wörtern keine Rolle spielen.
Eliminierung von Kettenregeln, die keinen Beitrag zur Erzeugung von Wörtern liefern. Kettenregeln werden wo es geht zu einer Regel zusammengefaßt.

Chomsky-Normalform

Eine Regel befindet sich in der Chomsky-Normalform, wenn ihre rechte Seite entweder aus genau zwei Nichtterminalen oder einem Terminalsymbol besteht. Zu jeder kontextfreien Grammatik existiert eine Grammatik in Chomsky-Normalform.

Greibach-Normalform

Eine Regel in der Greibach-Normalform besteht aus einem Terminalsymbol ganz links und n- Nonterminalsymbolen. Zu jeder kontextfreien Grammatik existiert eine Grammatik in Greibach-Normalform.

Eigenschaften kontextfreier Grammatiken

Aus einer kontextfreien Grammatik kann ein Ableitungsbaum gebildet werden. Hierbei wird jedes Nonterminal als Verzweigung gesehen, an dessen Ästen weitere Verzweigungen oder Terminalsymbole angeordnet sind. Sie spielen eine große Rolle im Compilerbau, da sie vom Compiler als innere Repräsentation eines Programmes aufgebaut werden. Sie stellen die Grundlage zur Erzeugung des Objektcodes des Programmes dar. Aus dem Ableitungsbaum wird ein Termbaum entwickelt, indem die Verknüpfungssymbole auf die Verzweigungen rutschen, so daß der ganze Baum nur noch aus Terminalen besteht. Der Termbaum kann dann relativ einfach in eine Folge von Assemblerbefehlen transformiert werden.

Eine Grammatik kann Ableitungen enthalten, die mehrdeutig interpretiert werden können. Hier kann es bei der Auswertung Probleme geben, da Vorrangregeln¹³beachtet werden müssen. Beim Entwurf von Programmiersprachen müssen diese Probleme berücksichtigt werden. Die Grammatiken zur Definition der Syntax der Sprache muß so aufgebaut sein, daß nur Eindeutige und korrekte Ergebnisse entstehen können. Eine Grammatik mit mehrdeutigen Aussagen läßt sich in eine eindeutige Grammatik überführen.

Pumping-Lemma

Für die Klasse der kontextfreien Sprachen kann ebenso wie für die Regulären Sprachen ein Pumping-Lemma genutzt werden um zu entscheiden ob die Wörter dieser Sprache nicht kontextfrei sind. Allerdings kann nicht festgestellt werden ob diese Sprache kontextfrei ist.

Abschlußeigenschaften

Die Klasse der kontextfreien Sprachen ist nicht gegeüber allen gängigen Operationen abgeschlossen¹⁴.

Abgeschlossen sind kontextfreie Sprachen gegenüber

Vereinigung
Konkatenation
Kleene-Stern-Produkt
Spiegelung

Nicht abgeschlossen sind sie gegenüber

Druchschnitt
Komplementbildung

Erweiterte Baccus-Naur-Form

Eine Darstellung von kontextfreien Grammatiken läßt sich auch mit der erweiterten Baccus-Naur-Form (EBNF) erreichen. Eine Grammatik in Baccus-Naur-Form ist folgendermaßen aufgebaut:

$\displaystyle G = (\Sigma, N, P, S)$

(1)

Hier ist $S \in N$ das Startsymbol und

eine endliche Menge von erweiterten Baccus-Naur-Regeln darstellt. Die Symbolik der Regeln beinhaltet auch Symbole wie $\vert$ , oder $\{\}^1_0$ und $\star$ , die wie bei den regulären Ausdrücken interpretiert werden. Eine Ableitung bei der ein Nonterminal durch ein Terminalsymbol ersetzt wird, wird auch Expansion genannt. Eine Ableitung bei der ein Nonterminal durch ein anderes ersetzt wird nennt sich Reduktion.

Die Klasse der Sprachen, die mit Erweiterten Baccus-Naur-Grammatiken erzeugt werden können ist genau die Klasse der kontextfreien Sprachen.

Syntaxdiagramme

Aus Grammatiken lassen sich Syntaxdiagramme erstellen. Diese werden in der Praxis sehr verbreitet verwendet um die Syntax von formalen Sprachen anschaulich darzustellen. Syntaxdiagramm stellen mit Hilfe von Pfeilen und Quadratischen Symbolen einen Fluß durch die Grammatik dar. Hierbei wird einen Alternative von Ersetzungen dargestellt indem mehrere Kästen parallel geschaltet werden. Eine Regel der Form $\{\}^*$ wird mit antiparallelen Pfeilen über dem Symbol dargestellt.

Reguläre Definition

Eine reguläre Definition ist eine kontextfreie Grammatik, die einen regulären Ausdruck erzeugt. Somit erzeugt eine reguläre Definition indirekt eine Sprache. Diese wird durch den von der regulären Definition erzeugten regulären Ausdruck erzeugt.

Kellerautomaten

Der Kellerautomat ist ein Automat mit einem Stackspeicher, in dem ein Symbol abhängig vom aktuellen Zustand und von der Eingabe abgelegt werden kann. Die formale Definition des Kellerautomaten lautet:

$\begin{displaymath}K = (\Sigma, S, \Gamma, \delta, s_0, \perp, F)\end{displaymath}$

mit den Elementen:

$\begin{eqnarray*} \Sigma &=& \mbox{Eingabealphabet}\\ S &=& \mbox{endliche Zu... ... \perp &=& \mbox{Bottomsymbol}\\ F &=& \mbox{Endzustandsmenge} \end{eqnarray*}$

Die Zustandsüberführung ist jetzt gegenüber der beim einfachen Automaten erweitert worden, da der Keller oder Stack noch bearbeitet wird. Die Speicherung auf dem Stack erfolgt in der Weise, daß das aktuelle Symbol vom Stack entfernt wird und ein neues Symbol gemäß Zustandsüberführung auf denselben gelegt wird. Der push-Befehl eines Kellerspeichers ist also aus vorhergehendem pop mit nachfolgendem push zusammengesetzt.

Die Zustandsüberführungsfunktion des Kellerautomaten ist allgemein aufgebaut aus:

$\begin{eqnarray*} \delta &=& (s_x, a_{\Sigma}, s_{Keller}, s_f, s_{Keller, neu}... ...es Automaten}\\ s_{Keller, neu} &=& \mbox{ neues Kellersymbol} \end{eqnarray*}$

Beim Übergang in den Endzustand kann das Kellerbottomsymbol gelöscht werden. Dieses ist für die Akzeptanz eines Wortes allerdings nicht notwendig. Das gänzliche Leeren des Kellers hätte in obigem Beispiel schon ausgereicht. Das Erreichen eines Endzustandes seitens des Automaten ist in diesem Falle gar nicht erforderlich, so daß die Menge F der Endzustände die leere Menge oder ganz weggelassen werden könnte. Die Klasse der Sprachen, die durch einen Kellerautomaten mit leerem Keller akzeptiert werden ist gleich der Klasse der Sprachen, die durch einen Kellerautomaten mit Endzustand akzeptiert werden.

Zu jedem Kellerautomaten läßt sich eine kontextfreie Grammatik konstruieren und umgekehrt. Jede kontextfreie Sprache kann durch einen Kellerautomaten mit nur einem Zustand (mit leerem Keller) akzeptiert werden. Es gibt also auch bei den Typ-2-Sprachen äquivalente generierende (Grammatiken) und akzeptierende ((Keller-)Automaten) Konzepte.

Ein allgemeines Verfahren, der Parser-Generator kann zu einer kontextfreien Grammatik einen Kellerautomaten konstruieren, der genau die von der Grammatik erzeugte Sprache konstruiert. Beim Akzeptieren eines Wortes mit diesem Kellerautomaten kann ein Ableitungsbaum für dieses Wort erzeugt werden. In der Praxis werden Kellerautomaten für den Compilerbau und bei der Sprachdefinition verwendet, da sie Syntaxtests in linearer Zeit ermöglichen.

deterministische Kellerautomaten

Der nichtdeterministische (Keller-) Automat kann in der praktischen Verwendung im Compilerbau einige Probleme verursachen. Beim nichtdeterministischen Kellerautomaten können sich für einen Zustandsübergang mehrere Möglichkeiten bieten. Der Automat muß im Durchschitt die Hälfte der Möglichkeiten durchlaufen, um festzustellen welche der Möglichkeiten überhaupt ``paßt''. Beim Großteil der durchlaufenden Fälle erfolgt das Backtracking, der Automat muß an eine zuvor gespeicherte Position zurückspringen, da die aktuell durchlaufene Möglichkeit das jeweilige Wort nicht akzeptiert. Beim nichtdeterministischen Kellerautomaten kann das Erkennen von Wörtern daher exponentiell lange dauern. Ein Eingabewort der Länge n kann

Schritte für seine Überprüfung durchlaufen. Aus diesem Grunde ist man an deterministischen Zustandsübergängen interessiert.

Aufzählbare und nicht abzählbare Mengen

Eine Menge heißt abzählbar, falls sie endlich ist, oder falls es eine bijektive Abbildung $f: M \rightarrow N_0$ gibt.

Jedem Element $m \in M$ muß eindeutig eine natürliche Zahl $f_{(m)}$ zugeordnet werden können. Alle Elemente aus M besitzen eine eindeutige Nummer, können also abgezählt werden.

Die Menge $Q = \{\frac{p}{q}\vert p,q \in Z, q \ne 0\}$ ist abzählbar. Hier kann jedem beliebigen Bruch eine eindeutige Zahl zugeordnet werden.

Jede Teilmenge einer abzählbaren Menge ist abzählbar. Falls eine Menge abzählbar ist, sind zwangsläufig Untermengen hiervon.

Nicht-oder überabzählbare Mengen

Eine Menge ist überabzählbar, falls sie nicht eindeutig in einer bijektiven Abbildung zugeordnet werden kann.

Jede Obermenge einer nicht abzählbaren Menge ist nicht abzählbar.

Die Menge der reellen Zahlen ist überabzählbar. Mit Hilfe der Diagonalisierung wird dieses bewiesen. Falls die Menge der reellen Zahlen im Intervall (0,1) der Menge $I = \{ x \in R \vert 0 < x < 1\}$ überabzählbar ist, so muß dieses auch für alle reellen Zahlen gelten.

Jedes $x \in I$ läßt sich als unendliche Dezimalzahl schreiben:

$\displaystyle x = 0,x_1x_2x_3...$

(2)

Falls I abzählbar ist, lassen sich alle Elemente von I abzählen:

$\displaystyle x_1$	$\textstyle =$	$\displaystyle 0,x_{11}x_{12}x_{13}...$	(3)
$\displaystyle x_2$	$\textstyle =$	$\displaystyle 0,x_{21}x_{22}x_{23}...$	(4)
$\displaystyle x_3$	$\textstyle =$	$\displaystyle 0,x_{31}x_{32}x_{33}...$	(5)

Jede Zahl von kann also eindeutig einer Zahl aus N (natürliche Zahl, Aufzählung) zugeordnet werden. Es läßt sich eine unendliche Dezimalzahl konstruieren:

$\displaystyle x_d$

$\textstyle =$

$\displaystyle 0,a_1a_2a_3...$

(6)

Für die Elemente der Dezimalzahl soll folgendes gelten:

$\displaystyle a_i = \left\{ \begin{array}{lll} 1, & falls & x_{ii} \ne 1\\ 2, & falls & x_{ii} = 1\\ \end{array}\right. \mbox{, f\uml {u}r alle i}$

(7)

Nach der Regel ist die i-te Dezimalziffer von 1 falls die i-te Ziffer der i-ten Zahl von (3) ungleich 1 ist. Falls sie ungleich 1 ist, ist sie gleich 2. Der Dezimalanteil der Zahl besteht also nur aus Einsen und Zweien, die durch die Diagonale der Abzählung 3 bestimmt ist.

ist eine belibige Zahl aus (3), so daß für die Regel (8) gelten muß. Dieses ist insofern ein Wiederspruch, da $a_i = x_{11} = 1$ falls $x_{11} \ne 1$ . Bei $x_{ii} = 1$ muß $x_{ii} = 2$ sein, was ebenfalls einen Widerspruch ergibt.

Turingautomaten

Ein Turingautomat ist durch den wahlfreien Zugriff auf den Speicher gekennzeichnet. Als Arbeitsspeicher wird hier das Eingabeband genommen. Der Turingautomat ist definiert durch:

$\begin{eqnarray*} TA &=& (\Sigma, S, \Gamma, delta, s_0, \char93 , F)\\ wobei... ...tzustand\\ \char93 &=& Blanksymbol\\ F &=& Endzustandsmenge \end{eqnarray*}$

Wenn die Zustandsüberführung (Turingprogramm, $\delta$ ) als Funtion dargestellt werden kann, heißt TA deterministisch. Falls es eine Relation (1:n) ist, heißt TA nichtdeterministisch. Das Turingprogramm wird geschrieben als Anweisung:

$\begin{displaymath}(s,a,s',b,m)\end{displaymath}$

Die Anweisung bedeutet, daß TA sich vorher im Zustand s, und der Schreib-Lesekopf unter dem Symbol a. TA geht jetzt in den Zustand über und überschreibt dabei das Symbol a mit dem Symbol b und führt dann die Bewegung m aus. Die Bewegung m kann l (links), r (rechts) oder - (keine Bewegung) sein.

Die Zustandsüberführung $\delta$ beschreibt also das Bearbeiten des Arbeitsbandes. Es gilt die Vereinbarung, daß jede Anweisung durch ein oder mehrere Blanks (#) begrenzt ist.

Jeder Turingautomat kann durch einen Kellerautomaten mit zwei Kellern simuliert werden.

Konstruktion für

Ein Automat, der die Sprache

$\begin{displaymath}L = \{a^nb^nc^n \vert n \ge 1\}\end{displaymath}$

akzeptiert, muß als Turingautomat ausgebildet werden, da L nicht kontextfrei ist. Diese Sprache wird nicht mehr von einem Kellerautomaten akzeptiert, da dieser mit Hilfe des Stacks zwar überprüfen kann, ob die Anzahl der a's gleich der Anzahl der b's ist, allerdings ist eine weitere Überprüfung auf die Anzahl der c's nicht möglich.

Linear beschränkte Automaten

Einem linear beschränkten Autmaten steht ein genau abgegrenzer Bereich des Arbeitsspeichers zur Verfügung. Dieses ist genau der Arbeitsspeicher, der für das Eingabewort zur Verfügung steht. Zur Begrenzung des Arbeitsspeichers wird das Symbol & als rechter Begrenzer eingeführt. Ein Eingabewort (w) wird also in der Form #w& auf das Band geschrieben. Hier ist # das Bandanfang-Symbol und & das Bandendesymbol.

Bei einem linear beschräntem Automaten darf das Programm diese Begrenzer nicht verändern und den rechten Begrenzer nicht überschreiten.

Das Programm darf also lesend auf das Band links vom Bandanfangssybol zugreifen, aber nicht über das Wortendesymbol (&) hinaus laufen.

Der linear-beschränkte nichtdeterministische Turingautomat wird auch als LBA (linear bounded automaton) bezeichnet.

Ein linear beschränkter Automat ist (quasi) äquivalent zu einer kontextsensitiven (Typ-1) Grammatik. Die Aussage ``quasi'' beruht darauf, daß Sprachen, die von linear beschränkten Automaten akzeptiert werden, daß leere Wort enthalten können. Eine kontextsensitive Sprache kann dieses nicht enthalten, da dieses nicht von monotonen Regeln erzeugt werden kann.

Aus der obigen Aussage folgt, daß der Turingautomat vollständig äquivalent zur Typ-0-Grammatik ist.

Das LBA-Problem

Jeder nichtdeterministische Turingautomat kann durch einen deterministischen simuliert werden. Allerdings weiß man bis heute nicht, ob ein nichtdeterministischer linear beschränkter Turingautomat immer in einen deterministischen Turingautomaten transformieren kann, der auch linear beschränkt ist. Dieses offene Problem ist das LBA-Problem der theoretischen Informatik.

Turing-Berechenbarkeit

Endliche Maschinen (Mealy-, Moore-) ordnen Eingabewörtern Ausgabewörter zu; sie berechnen damit eine Funktion. Ein Turing-Automat mit einer Ausgabefunktion wird zu einer Turing-Maschine. Mit Hilfe dieser Maschine läßt sich u.U. eine Funktion berechnen - diese ist dann Turing-Berechenbar.

Mit Hilfe der Turing-Maschine läßt sich die allgemeine mathematische Berechenbarkeit formal präzisieren. Das Turingband entspricht dem Speicher oder einem Blatt Papier für Notizen, Schreib- und Löschwerkzeuge entsprechen dem Schreib-/Lesekopf. Die Ausgangsdaten (gegebene Parameter) werden jeweils mit Hilfe eines bestimmten endlichen Verfahrens (Algorithmus, Programm) manipuliert. Hält das Programm schließlich an, steht das Ergebnis auf dem Blatt bzw. im Speicher.

Turing-Berechenbarkeit und Algorithmus

Ein Algorithmus ist ein formales Verfahren zur Lösung eines (Wort-) Problems. Dieses kann ein mathematisches Problem sein, daß mit Hilfe einer Maschine gelöst werden soll. Es gilt:

Eine Funktion (über einem Alphabet $\Sigma$ bzw. über ) ist algorithmisch berechenbar, falls es einen Algorithmus (eine Turingmaschine) gibt, der sie berechnet.

Universelle Turingmaschinen

Die universelle Turingmaschine (UTM) ist ein theoretisches Konzept für die Existenz universeller Rechner. Sie kann jede andere Turingmaschine einschließlich sich selbst auf deren Eingaben simulieren. Das heißt, daß die UTM als Eingabe zum einen die Turingmaschine erhält, die sie simuliert und zum anderen das Programm, daß die simulierte Turingmaschine ausführen soll.

Die Existenz dieser universellen Turingmaschine is die Grundlage für die Existenz universeller Rechner. Die CPU mit ihren Maschinenanweisungen läßt sich als universelle Turingmaschine auffassen. Sie kann andere Turingmaschinen simulieren, die z.B. eine mathematische Aufgabe lösen sollen. Das Programm, daß auf der CPU läuft ist die Turingmaschine, die die Aufgabe löst. Die Eingabeparameter des Programms sind die Eingabe für die simulierte Turingmaschine.

Weitere Berechenbarkeitsbegriffe

Neben der Turing-Berechenbarkeit können noch weitere Berechenbarkeitsbegriffe herangezogen werden. Diese gehen allerdings hinsichtlich ihrer Konzeption schon in die Prozeduralen Programmiersprachen hinein.

loop: Loop-Berechnungen erfolgen durch vorher festgelegtes Durchlaufen einer Schleife mit Berechungsanweisungen. Ein Loop-Programm terminiert aus diesem Grunde immer und ist somit total.
while: Die While-Berechnung unterscheidet sich dahingehend von der Loop-Berechnung, daß hier erst im Laufe der Berechnung ermittelt werden kann, wie oft die Berechnung wiederholt wird. While-Berechenbarkeit ist äquivalent zur Turing-Berechenbarkeit und zur Goto-Berechnung. Daher können diese Formen ineinander umgewandelt werden.
goto: Die Goto-Berechung erfolgt mit Hilfe von festgelegten Sprüngen zu Teilberechnungen. Sie ist äquivalent zur While- und zur Turing-Berechenbarkeit und kann in diese umgewandelt werden und umgekehrt.

Aufgrund der Äquivalenz von Goto- und While-Berechenbarkeit ist es möglich ein beliebiges Programm in einer prozeduralen Programmiersprache zu erstellen, daß ohne Goto-Sprünge auskommt.

Loop-berechenbare Funktionen sind total, das heißt sie terminieren immer und sind somit immer lösbar. Die Klasse der Loop-berechenbaren Funktionen ist eine Untermenge der While-, Goto- und Turing-Funktionen.

Aufgrund dieser Tatsachen wird die Churchsche These, nach der diese formalen Berechenbarkeitsbegriffe mit unserem intuitiven Verständnis von Berechenbarkeit übereinstimmen, allgemein akzeptiert.

Entscheidbarkeit

Bei der Berechenbarkeit von Mengen interessiert nur, ob ein spezielles Objekt zur Menge gehört oder nicht. Im Zusammenhang mit Mengen wird dann von Entscheidbarkeit gesprochen. Beim Berechnen einer Funktion wird mit einem Automaten das Akzeptieren einer Sprache simuliert.

Semi-Entscheidbarkeit

Eine Menge ist über einem Alphabet in Verbindung mit einer Grammatik entscheidbar, falls eindeutig festgestellt werden kann, ob die ein Subset des Alphabets darstellende Menge ein Wort im Sinne der Grammatik darstellt oder nicht.

ist entscheidbar, falls gilt:

$\begin{eqnarray*} X_L: \Sigma^* & \rightarrow & \{0,1\}\\ \\ X_L(w) & = & \l... ... falls & w \in L\\ 0, & falls & w \notin L \end{array}\right. \end{eqnarray*}$

Dagegen ist semi-entscheidbar für:

$\begin{eqnarray*} X_L': \Sigma^* & \rightarrow & \{0,1\}\\ \\ X_L'(w) & = & ... ... \in L\\ undefiniert, & falls & w \notin L \end{array}\right. \end{eqnarray*}$

Die Voraussetzung für die Entscheidbarkeit ist also, daß auf jeden Fall festgelegt ist, ob ein akzeptiert werden kann oder nicht. Für die semi-Entscheidbarkeit genügt der Beweis, daß ein Wort akzeptiert wird.

Reduzierbarkeit von Mengen

Bei Feststellung der Entscheidbarkeit von konkreten Mengen ist es oft hilfreich, falls die Frage nach der Entscheidbarkeit einer Menge auf die Entscheidbarkeit einer anderen Menge zurückgeführt werden kann. Hieraus kann dann auf die Entscheidbarkeit von geschlossen werden.

Das Postsche Korrespondenzproblem

Das Postsche Korrespondenzproblem ist insofern hilfreich, als das andere (unentscheidbare) Probleme auf dieses Problem reduziert werden können und damit bewiesen werden kann, daß diese unentscheidbar sind.

Unentscheidbare und semi-entscheidbare Probleme

Korrektheitsproblem

Das Korrektheitsproblem ist ein nichtentscheidbares Problem. Es besagt, daß es nicht möglich ist, automatisiert festzustellen ob ein beliebiges Programm ein Problem korrekt löst.

Das Äquivalenzproblem

Das Äquivalenzproblem ist der Beweis ob zwei Versionen eines Programmes dasselbe Problem berechnen. Dieser Beweis würde es ermöglichen mit Hilfe von weiteren Untersuchungen dasjenige Programm zu ermitteln, welches nach anderen Kriterien (Benutzerfreundlichkeit) besser zur Problemlösung geeignet wäre.

Komplexizität

Auch prinzipiell lösbare Probleme können sich in der realen Welt als unlösbar herausstellen. Falls die Laufzeit des Algorithmus zur Lösung des Problems exponentiell mit der Größe der Eingabewörter anwächst kann die Lösung des Problems in einer endlichen Zeitspanne nicht mehr zu erreichen sein.

Die Darstellung der Komplexizität erfolgt mit Hilfe der -Notation. Diese legt die Laufzeiten in Abhängigkeit von der Eingabe wie folgt fest:

: konstant, also unabhängig von der Eingabe,
: logarithmisch,
: linear,
: n-log-n,
: quadratisch,
: kubisch,
: exponentiell.

Die P-NP-Frage

P ist die Klasse der Probleme, die mit deterministischen Turingmaschinen in Polynomzeit (

) berechenbar sind. NP ist die Klasse aller Probleme, die mit nichtdeterministischen Turingmaschinen in Polynomzeit berechenbar sind. Bei der Transformation von nichtdeterministischen Turingmaschinen in äquivalente deterministische Turingmaschinen werden die Laufzeiten exponentiell und damit praktisch unakzeptabel.

Viele Probleme, die so nicht in akzeptabler Zeit gelöst werden können wie z.B. das Travelling Salesman werden in der Praxis durch Heuristiken, die auf Erfahrungen beruhen und suboptimal sind, zufriedenstellend gelöst.