Anton – Seite 13 – Informatik an der Fernuni

17. Juni 201324. November 2025

TIA: Flussdiagramme, Maschinen und berechenbare Zahlenfunktionen (Lernziele KE1, Update 2)

Update: Einwand von Felix aufgenommen.

Update: Marion hat einen Fehler bei der Berechnung der $ES$ gefunden. Danke!

Update: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz.

Update: Hinweis darauf, dass das erste Register bei der Eingabecodierung $EC$ für eine Maschine belegt werden kann (wir haben keine Einschränkungen), aber nicht durch die Eingabecodierung für eine Registermaschine!

Als ich die ersten Beiträge zur Kurseinheit 1 von Teil A der theoretischen Informatik geschrieben habe, orientierte ich mich an den Themen. Entstanden sind damit die Unterbeiträge:

Irgendwann, gegen Ende der Kurseinheit 5 habe ich gemerkt, dass es vielleicht sinniger ist anhand der Lernziele zu gehen. Das bringt etwas mehr Struktur in die Beiträge und wirft einen roten Faden durch das Skript.

Als ich dann bei Kurseinheit 7 von Teil B angelangt war, hat sich mein Entschluss gefestigt die alten Beiträge ebenfalls zu überarbeiten. Was ich hiermit also tun möchte.

Lernziel 1

Angabe und Erläuterung der Definition des Flussdiagramms

Ich würde vorschlagen, wir definieren wieder und erklären die Definition Zeile für Zeile: das Flussdiagramm ist ein 4-Tupel $F=(Q,D,\sigma,q_o)$

$Q$ als Markenmenge
$D$ als Datenmenge
$q_0$ als Startmarke
$\sigma$

zu jeder Marke gehört entweder eine Zuweisung

$(f,p)$

oder eine Verzweigung/Test

$(S,p,p^{‚})$

Beispiel gefällig?

Beispiel: $F_1=(Q,D,\sigma,q_0)$ mit

$Q=\{1,2,3,4\}$: wir haben nur vier Marken im Flussdiagramm

$D=\mathbb{N}^2$: wir operieren auf max. zweistelligen, natürlichen Zahlen

$q_0=1$: die Anfangsmarke ist $1$

Und nun kommt unsere Funktion, die jeder Marke eine Operation zuweist. Das macht das Flussdiagramm nämlich erst aus.

$\sigma(1)=(y=1,2)$ (Zuweisung)

$\sigma(2)=(y>x,4,3)$ (Verzweigung/Test)

$\sigma(3)=(y=y+1,2)$ (Zuweisung)

$\sigma(4)=HALT$ (Haltemarke)

Und wenn wir $F_1$ auf Papier bringen:

Nicht so schwer, oder? Was tut das Flussdiagramm $F_1$? Nichts besonderes: es zählt nur $y$ hoch bis es größer ist als $x$. Nicht besonders sinnvoll, aber kurz (ich bin faul, sorry) und anschaulich.

Antwort zum Lernziel: Ein Flussdiagramm besteht aus einer Marken- und Datenmenge, einer Startmarke und einer Funktion, die jeder Marke aus der Markenmenge eine Zuweisung oder eine Verzweigung zuordnet.

Lernziel 2

Angabe und Erläuterung der Semantik des Flussdiagramms

Semantik? Bedeutung! Das Flussdiagramm $F$ definiert nämlich nichts anderes als eine Funktion $f_F$, die aus den Parametern (oben waren es $x$ und $y$) in einer Endkonfiguration (so denn es eine gibt) ein Ergebnis generiert. Die Semantik eines Flussdiagramms gliedert sich in folgende Begriffe:

Konfiguration: z.B. Anfangs- und Endkonfiguration sowie Zwischenkonfigurationen
Einzelschrittfunktion: Übergang in einem Berechnungsschritt von einer Konfiguration in eine andere
Schrittzahlfunktion: $div$ wenn es zu einer Eingabe keine Endkonfiguration gibt oder die Anzahl der Schritte, die zu einer Eingabe bis zur Endkonfiguration geführt haben
Gesamtschrittfunktion: Endkonfiguration zu einer Eingabe. Wenn sie existiert. Ansonsten $div$.
Semantik: Das Ergebnis

Beispiel: $F_1=(Q,D,\sigma,q_0)$ (von oben)

Sagen wir, wir starten $F_1$ mit $x=2$ und $y=0$.

Anfangskonfiguration: $(1,(2,0))$ und Endkonfiguration: $(4,(2,3))$ (Zwischenkonfigurationen lasse ich mal weg)
Einzelschrittfunktion: z.B. $ES(1,(2,0)=(2,(2,1))$. Nach einem Schritt befinden wir uns in Marke $2$ und haben nur $y=1$ gesetzt. Würden wir aber z.B. $ES^6(1,(2,0))$ nehmen, so müssten wir fünf Berechnungsschritte im Flussdiagramm ausführen und wären bei

$\begin{align}ES^6(1,(2,0))&=ES^5(2,(2,1))\\&=ES^4(3,(2,1))\\&=ES^3(2,(2,2))\\&=ES^2(3,(2,2))\\&=ES(2,(2,3))\\&=(4,(2,3))\end{align}$

(Update: Nach Einwand von Felix korrigiert. Danke!)

Schrittzahlfunktion: $SZ(1,(2,0))=7$. Nach $7$ Schritten kommen wir, ausgehend von der Anfangskonfiguration $(1,(2,0))$ in die Endkonfiguration $(4,(2,3))$.
Gesamtschrittfunktion: $GS(1,(2,0))=(4,(2,3))$. Die Endkonfiguration zur Anfangskonfiguration $(1,(2,0))$ ist eben $(4,(2,3))$ und damit unsere Gesamtschrittfunktion.
Semantik: $f_{F_1}(2,0)=(2,3)$. Das Ergebnis der harten Arbeit unseres Flussdiagrsmms.

Auch nicht viel schwerer als Lernziel 1.

In einem alten Beitrag habe ich das bereits für Registermaschinen aufgegriffen.

Antwort zum Lernziel: das Flussdiagramm definiert eine Funktion $f_F$ (die Semantik des Flussdiagramms) auf der Datenmenge des Flussdiagramms, welche von einer Anfangskonfiguration (Startmarke, Eingabe) nach endlich vielen Schritten zu einer Endkonfiguration (Endmarke, Ausgabe) führt. Oder auch nicht.

Die Belegung der Variablen im Flussdiagramm ist das Ergebnis der Berechnung, es gilt dann $f_F(Eingabe)=Ausgabe$. Gibt es zu der Eingabe kein Ergebnis, so ist $f_F(Eingabe)=div$.

Lernziel 3

Angabe und Erläuterung der Definition und Semantik einer Maschine

Kommen wir nun zu den Maschinen. Warum reicht uns das Flussdiagramm von oben nicht? Weil die Datenmenge $D$ des Flussdiagramms meistens nicht mit der Definitions- oder Bildmenge unserer durch das Flussdiagramm darzustellenden Funktion übereinstimmen wird. Wir brauchen hier also zusätzlich noch ein paar andere Dinge: eine Maschine ist ein 5-Tupel mit $M=(F,X,Y,EC,AC)$.

$F$ ist ein Flussdiagramm (siehe oben)

$X$ ist eine Eingabe- und $Y$ eine Ausgabemenge.

$EC:X\rightarrow D$: Eingabecodierung. Es ist nichts weiter als eine Funktion, die aus einem Element aus $X$ eine Eingabecodierung aus $D$ für unser Flussdagramm ausgibt. Under Flussdiagramm nimmt nämlich keine Elemente aus $X$, sondern nur aus $D$ entgegen.

$AC:D\rightarrow Y$: Ausgabecodierung. Ebenfalls nur eine Funktion, die hier jedoch zu einem Element aus $D$, der Datenmenge des Flussdiagramms ein Element aus der Ausgabemenge $Y$ zuweist.

Damit berechnet $M$, unsere Maschine also eine Funktion $f_M=AC(f_F(EC))$

Das letztere erschließt sich wahrscheinlich nicht sofort. Aber wie können das an einem Beispiel etwas anschaulicher gestalten.

Achtung (Update): während wir bei der Eingabecodierung bei einer Maschine es zulassen, dass wir das erste Register belegen, tun wir das keinesfalls bei einer Registermaschine! Das ist bei der Initialbelegung durch die Funktion $EC$ nicht zulässig, denn es fungiert als Ergebnisregister und ist initial immer mit $0$ belegt!

Beispiel: Maschine $M$ mit dem Flussdiagramm von oben, $x=2$ und den zusätzlichen Mengen und Funktionen

$X,Y=\mathbb{N}$: die Mengen unserer Eingabe- und Ausgabecodierungen für unsere Maschine sind nicht mehr Tupel ($\mathbb{N}^2$), wie sie das Flussdiagramm brauchst, sondern bestehen nur noch aus einem einzigen Element.

$EC:X\rightarrow D$ mit $EC(x)=(x,0)$.

$AC:D\rightarrow Y$ mit $AC(x,y)=y$

Wir können unsere Maschine $M$ also einfach nur mit $x$ füttern und erhalten durch die Eingabefunktion $EC$ auch unser $y$ für die Eingabe in unser Flussdiagramm. Ähnliches gilt für die Ausgabecodierung: unser Flussdiagramm gibt uns $(x,y)$ als Ausgabe heraus, was wir mit der Funktion $AC$ in $y$ umwandeln.

Setzen wir also $x=2$ mal ein:

$EC(x)=(2,0)$. Damit füttern wir unser Flussdiagramm und bekommen als Ausgabe des Flussdiagramms $f_F=(2,3)$. Das werfen wir in unsere Ausgabecodierung $AC(2,3)=3$ und haben die Ausgabe unserer Maschine $f_M$.

Der letzte Punkt unserer Maschine mit ausgefülltem $x=2$ bedeutet also:

$\begin{align}f_M&=AC(f_F(EC(2)))\\&=AC(f_F(2,0))\\&=AC(2,3)\\&=3\end{align}$

That’s it.

Antwort zum Lernziel: eine Maschine tut für uns also nichts anderes, als es uns zu ermöglichen nicht mehr auf der Datenmenge $D$ des Flussdiagramms operieren zu müssen. Durch die „Eingabecodierungs-Funktion“ $EC$ können wir aus einer beliebigen Eingabemenge $X$ in die Datenmenge $D$ des Flussdiagramms abbilden und so unser Flussdiagramm mit einer passenden Eingabe füttern.

Mittels der „Ausgabecodierungs-Funktion“ $AC$ gelingt uns auch der Rückweg aus der Ausgabe des Flussdiagramms (die ja ein Element aus $D$ ist) in die Ausgabemenge $Y$.

Damit ist die Semantik einer Maschine die Funktion $f_M\subseteq X\rightarrow{Y}$, die mit Hilfe von $EC$ und $AC$ die Mengen $X$ und $Y$ von, bzw. in die Datenmenge $D$ für das Flussdiagramm überführt. Es gilt somit $f_M=AC(f_F(EC))$ wenn wir von einer Anfangskonfiguration zu einer Endkonfiguration kommen. Ansonsten ist $f_M=div$.

Lernziel 4

Angabe und Erläuterung der Definition einer Registermaschine

Kommen wir nun zu den Registermaschinen. Den eig. Stars dieser Kurseinheit. Ich hatte bereits in diesem Beitrag etwas zum Thema geschrieben. Es macht also keinen Sinn das hier noch einmal zu Wiederholen. Daher: bitte dort nachlesen und wiederkommen 😉

Update: nicht vergessen, die Eingabecodierung für eine Registermaschine belegt nicht das erste Register $R_0$!

$EC^{(k)}(x1,…,x_k):=(0,x_1,…,x_k)$

Ebenso ergeht es uns mit der Ausgabecodierung: uns ist egal, was in den anderen Registern steht, wir finden nur das erste Register spannend:

$AC(a_0,a_1,…):=a_0$

Antwort zum Lernziel: die Registermaschinen bestehen aus Registern mit durch die Eingabecodierung induzierten Registerbelegungen und der „Ausgabecodierungs-Funktion“, welche uns das 1. Register (Register $R_0$) der Registermaschine als Ausgaberegister festlegt. Dadurch ist es uns nur möglich die Register $R_1-R_m$ mittels Eingabecodierung zu belegen.

Die Registermaschine verfügt nur über drei Grundoperationen: Addition von $1$, ~~Subtraktion~~ arithmetische Differenz und Test auf $0$.

Lernziel 5

Angabe und Erläuterung der Definition einer verallgemeinerten Registermaschine

Auch die Erläuterungen zur verallgemeinerte Registermaschine sind hier zu finden. Daher kümmern wir uns nur um das Lernziel.

Antwort zum Lernziel: Durch die verallgemeinerte Registermaschine ist es uns möglich weitaus mehr Operationen als die Grundoperationen Addition und Subtraktion von $1$, sowie Test auf $0$ durchzuführen.

Diese Operationen werden jedoch aus den Grundoperationen zusammengesetzt und erlauben es uns Registerinhalte miteinander zu vergleichen oder Registern Werte zuzuweisen, die durch Funktionen berechnet wurden (wobei Registerinhalte der Registermaschine selbst als Parameter dieser Funktion fungieren können).

Lernziel 6

Angabe der Definition einer berechenbaren Zahlenfunktion

Ich gebe mal ganz frech die Definition aus dem Skript wieder:

Eine Funktion $f:\subseteq\mathbb{N}^k\rightarrow\mathbb{N}$ heißt berechenbar wenn es eine $k$-stellige Registermaschine $M$ gibt, die sie berechnet, so dass gilt: $f=f_M$.

Das ist eine der zentralen Definitionen im Teil A der theoretischen Informatik und findet sich auch häufig als Frage in den Protokollen der mündlichen Prüfung wieder: diese Definition sagt uns, dass wir eine Funktion dann berechenbar nennen können, wenn wir eine Registermaschine angeben, die sie berechnet und im Endeffekt auf die Grundoperationen Addition und Subtraktion von $1$ sowie Test auf $0$ zurückführt.

Beispiel: $f(x,y)=x+y$

Wollen wir also nachweisen, dass die Funktion $f$ berechenbar ist, so müssen wir eine Registermaschine inkl. Flussdiagramm angeben, dass uns die gleiche Ausgabe in Register $R_0$ liefert, wie die Funktion $f$.

Für Details und den Beweis, dass die Addition zweier Register ($f(x,y)=x+y$) berechenbar ist, empfehle ich euch hier den alten Beitrag zum Thema.

Antwort zum Lernziel: Wir können eine Funktion mit $k$Parametern also berechenbar nennen wenn wir sie mit einer $k$-stelligen Registermaschine und der Grundoperationen innerhalb eines Flussdiagramms berechnen können., so dass gilt: $f = f_M$.

Lernziel 7

Zeigen, dass eine Funktion berechenbar ist

Das Thema wurde ebenfalls hier detaillierter besprochen und gezeigt wie man eine Funktion (das angesprochene Beispiel mit der Addition zweier Register) als berechenbar nachweist. Ich begnüge mich also hier mit dem letzten Lernziel dieser Kurseinheit.

Antwort zum Lernziel: Um zu beweisen, dass eine Funktion berechenbar ist, muss man diese am Ende nur mit den Grundoperationen Subtraktion und Addition von $1$ und Test auf $0$ abbilden können.

Hat man z.B. die Addition mittels dieser Grundoperationen nachgebildet und mittels vollständiger Induktion bewiesen, dass sie für alle Werte das gewünschte Ergebnis liefert, so kann man diese komplexe Operation nun in seiner verallgemeinerten Registermaschine für weitere Beweise anderer Funktionen nutzen.

Z.B. kann man ausgehend von den Grundoperationen die Addition zweier Register $x+y$ beweisen und anschließend mit der Addition den Beweis der Multiplikation $x\cdot y$ angehen. Mit der Multiplikation gelingt uns dann das Beweisverfahren für die Exponentialfunktion $x^y$, usw.

Die Lernziele von Kurseinheit 1 haben wir damit durch. Noch 6 und der Kurs ist komplett 😉 Bei Fehler wie immer: ASAP in die Kommentare damit falsches Zeug nicht so lange online bleibt!

14. Juni 201325. November 2025

TIB: Kontextfreie Sprachen und Kellerautomaten (Lernziele KE7 3/3, Update 1)

Update: Fehler im Automaten behoben.

Letzter Beitrag zum Thema… ich tippe besonders langsam, versprochen 😉

Lernziel 5

Was sind determinierte Kellerautomaten?

Wir könnten zwar mit nichtdeterministischen Kellerautomaten leben und würden es sogar. Aber es gibt da ein Problem: wir können sie technisch nicht realisieren.

Den determinierten Kellerautomaten hatten wir im vorherigen Beitrag auch bereits definiert. Uns interessiert deshalb nicht was sie sind, sondern vielmehr wie sie sich von nichtdeterministischen Kellerautomaten unterscheiden und was das für Auswirkungen auf die erkannte Sprachklasse hat.

Eine echte Teilmenge der von nichtdeterminierten Kellerautomaten erkannten, kontextfreien Sprachen ist die deterministische kontextfreie Sprache:

Deterministisch kontextfrei

Eine Sprache ist deterministisch kontextfrei wenn es einen determinierten Kellerautomaten gibt, der sie erkennt.

Das Erkennen bedeutet folgendes:

Wenn $L\subseteq\Sigma^{*}$ eine deterministisch kontextfreie Sprache ist, dann gibt es einen Kellerautomaten $A=(\Sigma,\Gamma,\$,Q,q_0,\{q_{+}\},\delta)$ mit einem Zustand $q_{-}\in Q$, so dass für alle Worte $\omega\in\Sigma$ gilt:

$\omega\in L\Leftrightarrow (q_0,\omega\$,\$)\vdash^{*}(q_{+},\$,\epsilon)$

Das Wort $\omega$ ist Teil der deterministisch kontextfreien Sprache wenn es eine Überführungsfolge im Automaten $A$ gibt, die ausgehend vom Anfangszustand in einen akzeptierenden Endzustand mündet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.

$\omega\notin L\Leftrightarrow (q_0,\omega\$,\$)\vdash^{*}(q_{-},\$,\epsilon)$

Das Wort $\omega$ ist nicht Teil der deterministisch kontextfreien Sprache wenn es eine Überführungsfolge im Automaten $A$ gibt, die ausgehend vom Anfangszustand in einen nicht-akzeptierenden Endzustand mündet und die Eingabe zu Ende gelesen wurde, wobei der Keller leer ist.

Sie ist zudem auch noch eindeutig:

Jede deterministisch erkannte Sprache ist eindeutig*.

* erinnert Ihr euch noch an die Eindeutigkeit? Fall nicht: jedes abgeleitete Wort einer eindeutigen Sprache/Grammatik hat nur einen einzigen Ableitungsbaum.

Wir zeigen gleich, dass die deterministischen Automaten weniger leistungsfähig sind. Folgende Überlegungen sind notwendig:

1. ein deterministischer Kellerautomat akzeptiert nur Worte, die er zu Ende liest. Wir müssen daher unseren deterministischen Automaten entsprechen ummodellieren und die Szenarien vermeiden, wo der Automat nicht weiterlesen kann:

a) Keller leer bevor Eingabe zu Ende.

Lösung: neues Keller-Leerheits-Zeichen, dass nie gelöscht wird.

b) keine Folgekonfiguration für aktuelle Konfiguration vorhanden

Lösung: Vervollständigen von $\delta$, so dass wir zu jeder Möglichkeit einen Folgezustand haben

c) das Erreichen eines Zyklus, wo der Kopf nicht bewegt wird

Lösung: Erkennen und vermeiden des Zyklus.

2. Wir haben einen ausgezeichneten, positiven Endzustand: entweder er akzeptiert das Wort und wir landen in $q_{+}$ oder nicht und wir landen in $q_{-}\in Q$.

Mit der Vorarbeit aus dem letzten Beitrag, ist es nicht schwer diese weiteren Einschränkungen nachzuvollziehen.

Der Beweis für die Komplementbildung gelingt durch simples Vertauschen der Zustände $q_{+}$ und $q_{-}$, so dass wir diese Eigenschaft zusammenfasen können:

Sei $L\subseteq\Sigma^{*}$ deterministisch kontextfrei, so ist es auch $\Sigma^{*}\setminus L$.

Antwort zum Lernziel: Kellerautomaten (PDAs) sind endliche Automaten, die durch einen Kellerspeicher erweitert wurden. Bei einem Kellerautomaten wird ein Wort dann erkannt wenn der Keller leer ist oder der Automat in einem Endzustand landet (oder beides gleichzeitig).

Für einen determinierten Kellerautomaten gilt zudem, dass es für jedes Eingabezeichen und jedes oberste Kellerzeichen nur einen Zustandsübergang gibt, so dass der Kellerautomat den Berechnungsweg nicht zufällig wählen kann. Ist das nicht der Fall und gibt es zu einem Eingabezeichen und einem obersten Kellerzeichen mehrere mögliche Folgezustände, so ist der Kellerautomat nichtdeterministisch.

Für eine deterministisch kontextfreie Sprache $L$ bedeutet es, dass wir in jedem Fall für ein Wort $\omega\in L$ nach endlich vielen Schritten die Endkonfiguration $(q_{+},\$,\epsilon)$ (ausgewiesener Endzustand, Ende der Eingabe, leerer Keller) oder für ein Wort $\omega\notin L$ $(q_{-},\$,\epsilon)$ (beliebiger Zustand aus $Q$, Ende der Eingabe, leerer Keller) erreichen.

Lernziel 6

Ist jede kontextfreie Sprache deterministisch? Mit Begründung!

Ein (für mich) etwas verständlicheres Beispiel habe ich in den Folien der HU-Berlin gefunden und würde das hier gerne anbringen. Nehmen wir zwei deterministisch kontextfreie Sprachen (DCFL), die von einem determinierten Automaten erkannt wird, z.B.

$L_1=\{a^i b^j c^k\mid i\neq j\}\in DCFL$ sowie

$L_2=\{a^i b^j c^k\mid j\neq k\}\in DCFL$.

Beide Sprachen sind deterministisch kontextfrei. Wir können also einen deterministischen Kellerautomaten angeben, der sie erkennt.

Um $L_1$ zu entscheiden, können wir uns z.B. darauf beschränken die $a’s$ einzulesen, $A’s$ in den Keller zu schreiben und anschließend die $b’s$ einzulesen und die $A’s$ aus dem Keller zu entfernen. Es sind drei Fälle zu unterscheiden:

1. Gab es weniger $a’s$ als $b’s$, so haben wir noch $b’s$ auf dem Eingabeband, während der Keller bereits leer ist und alles ist gut.

2. Gab es mehr $a’s$ als $b’s$, so haben wir keine $b’s$ auf dem Eingabeband, während noch $A’s$ im Keller sind und alles ist immernoch gut.

3. Gab es die gleiche Anzahl $a’s$ und $b’s$, so haben wir einen leeren Keller just in dem Moment, wo wir keine $b’s$ auf dem Eingabeband haben und das Wort wird abgelehnt.

Das gleiche Verfahren klappt auch mit $L_2$ (nur mit $b’s$ und $c’s$ statt mit $a’s$ und $b’s$).

Schauen wir uns doch eine weitere Sprache an:

$L_1\cup L_2 = \{a^i b^j c^k\mid i\neq j$ oder $j\neq k\}\in CFL\setminus DCFL$.

Wie man sieht, ist das eine Vereinigung der beiden Sprachen $L_1$ und $L_2$. Um das etwas anschaulicher zu machen, schauen wir uns die Mengen doch einmal mit $1\leq i,j,k\leq 2$ an:

$L2_1=\{abbc,abbcc,aabc,aabcc\}$

$L2_2=\{abcc,abbc,aabcc,aabbc\}$

$L2_1\cup L2_2 = \{abbc,abbcc,aabc,aabcc,abcc,aabbc\}$

Während wir für für $L2_1, L2_2$ und die Vereinigung der beiden Sprachen $L2_1\cup L2_2$ sogar einen endlichen Automaten angeben können, der sie erkennt (wir erinnern uns: das ist genau der Grund warum alle endlichen Sprachen sogar regulär sind, ein akzeptierender Zustand pro Wort reicht im endlichen Automaten aus um die Sprachen zu erkennen), gelingt es uns bei $i,i,k\in\mathbb{N}$ nur für $L_1$ sowie $L_2$ einen Kellerautomaten anzugeben, der die Sprache erkennt (wir müssen die Anzahl der Buchstaben beobachen können und können das nur mindestens mit einem Kellerautomaten. Mindestens weil Turingmaschinen als stärkstes Berechnungsmodell selbstverständlich auch gehen, denn sie können ja selbst Typ-0-Sprachen erkennen).

Weit mehr Probleme macht uns die Vereinigung! Das Problem mit ihr ist: sie ist zwar kontextfrei, aber nicht deterministisch kontextfrei. Denn dafür können wir keine deterministische Kellermaschine angeben, sie sie erkennt.

Woran liegt das? Wie wir oben gesehen haben, beobachten wir mit dem Keller nur eine Variable (die Anzahl unserer ersten, eingelesenen Buchstaben) und können so eine andere abhängig von dieser entscheiden. Das ist bei den Sprachen $L_1$ und $L_2$ ja kein Problem. Bei $L_1\cup L_2$ haben wir jedoch drei Variablen, die von einander abhängig sind. Denn wir müssen $j$ in Abhängigkeit von $i$ und $k$ in Abhängigkeit von $j$ prüfen. Das war’s also mit dem Determinismus, denn wir haben mehrere Wege, die wir beschreiten müssen um am Ende einen zu finden, der funktioniert.

Die kontextfreie Grammatik für $L_1\cup L_2$ ist:

$S\rightarrow{DC \mid AE \mid B}$

$D\rightarrow{F\mid G}$

$F\rightarrow{aF \mid aFb \mid a}$

$G\rightarrow{Gb \mid aGb\mid b}$

$C\rightarrow{cC\mid\epsilon}$

$A\rightarrow{aA\mid\epsilon}$

$E\rightarrow{H\mid I}$

$H\rightarrow{bH\mid bHc\mid b}$

$I\rightarrow{Ic \mid bIc \mid c}$

$B\rightarrow{J \mid K}$

$J\rightarrow{aJ\mid aJc\mid aL}$

$K\rightarrow{Kc\mid aKc\mid Lc}$

$L\rightarrow{bL\mid\epsilon}$

Und daraus können wir den zugehörigen Automaten nach dem Schema aus dem vorherigen Beitrag bauen:

Download: AiBjCk_NPDA_JFLAP-Datei

Damit haben wir auch eine wesentliche Aussage für das nächste Lernziel herausgearbeitet: dass wir keinen deterministischen Automaten für $L_1\cup L_2$ angeben können liegt daran, das die deterministisch kontextfreien Sprachen zwar abgeschlossen sind bzgl. Schnitt und Komplement, aber nicht gegen Vereinigung, Durchschnitt, Spiegelung und Konkatenation! Und das obere Beispiel war die Vereinigung. Beispiele für Durchschnitt, Spiegelung und Konkatenation überlasse ich erstmal euch 😉

Zusammengefasst: Wir haben mit dem deterministischen Kellerautomaten, welche die Sprache erkennt, tatsächlich eine Beschneidung der Möglichkeiten, die uns ein nichtdeterministischer Kellerautomat bietet: wir können nicht mehr zwischen Berechnungspfaden wählen und sind an unsere Wahl „gebunden“. War sie falsch, so landen wir in einer Sackgasse und damit war es das. Bei einem nichtdeterministischen Automaten haben wir währenddessen (durch mehrere Folgekonfigurationen für eine Konfiguration) bereits andere Wege parallel beschritten, wo uns einer (wenn wir einen korrekten Automaten angegeben haben) schon zur Lösung führen wird. War eine Berechnung falsch, so landen wir auf diesem einen Weg in einer Sackgasse und … es ist uns egal. Wir haben ja noch genug andere Wege, die wir parallel beschreiten.

Hauptsache wir können beweisen, dass min. einer dieser Wege zu einem Ergebnis führt und entscheidet ob ein Wort sich in der Sprache befindet. Tut es das nicht, kann der nichtdeterministische Automat von uns aus solange weiterrechnen, bis er schwarz wird.

Ein Blick aus einer anderen Brille: Um bei der Sprache $L_1\cup L_2$ entscheiden zu können ob ein Wort tatsächlich zur Sprache gehört oder nicht, ist der Algorithmus wirklich einfach: Wir zählen die $a’s$, $b’s$ und $c’s$, speichern die Anzahl auf dem Hilfsband und vergleichen die drei Variablen nachdem wir die Eingabe vollständig eingelesen haben miteinander. Ihr habt sicher schon eine TM im Kopf, die das macht. Während wir das also mit einer DTM problemlos machen können, schaffen wir das mit einem PDA durch die Einschränkungen leider nicht.

Antwort zum Lernziel: Nicht jede kontextfreie Sprache ist deterministisch. Es gibt kontextfreie Sprachen, die aufgrund ihrer Struktur nicht von einem PDA erkannt werden können weil ihr Aufbau von mehreren Variablen abhängt, diese jedoch nicht durch einen einzigen Kellerspeicher deterministisch abgebildet werden können. Erst durch das Beschreiten mehrerer Berechnungspfade ist es möglich auch mehrere Variablen in die Betrachtung einzubeziehen und aus der so generierten Vielzahl an Pfaden die Aussage zu treffen, dass einer in jedem Fall zum Ziel führt wenn das Wort sich in der Sprache befindet.

Eine solche kontextfreie, aber nicht deterministische Sprache lässt sich durch Vereinigung, Konkatenation, Durchschnitt oder Spiegelung einer oder mit mehreren deterministisch kontextfreien Sprachen erzeugen, da die Sprachklasse der deterministisch kontextfreien Sprachen nicht abgeschlossen gegen diese Operationen ist.

Lernziel 7

Sind die kontextfreien bzw. deterministisch kontextfreien Sprachen abgeschlossen unter Vereinigung, Durchschnitt, Komplement und Schnitt mit regulären Mengen?

Was soll ich hier schreiben? Reicht die Tabelle aus dem Skript? 😉 Ihr solltet euch noch einmal vor Augen führen, wie die Sprachklassen zusammenhängen und die Beziehungen zwischen Unter- und Oberklasse sind. Dann wird euch auch deutlich warum diese gegen gewisse Operationen nicht abgeschlossen sein können. Vielleicht schreibe ich später noch ein paar Sätze dazu, aber bis dahin:

Antwort zum Lernziel:

	kontextfrei	deterministisch
Vereinigung	+	–
Durchschnitt	–	–
Komplement	–	+
Konkatenation	+	–
Stern	+	–
Schnitt mit regulären Mengen	+	+

Lernziel 8

Welche der folgenden Probleme sind für kontextfreie Grammatiken entscheidbar/unentscheidbar? Wortproblem, Endlichkeitsproblem, Leerheitsproblem?

Hier sollten wir einige Probleme auf den Mengen entscheiden können, diese sind:

Wortproblem: ob sich ein Wort $\omega$ in der Sprache $L$ befindet (oder nicht).
Inklusion: ob die Worte einer Sprache $L_1$ in einer anderen Sprache$L_2$ enthalten sind
Äquivalenz: ob die Sprache $L_1$ die gleiche Sprache wie $L_2$ ist.
Leerheit: ob die Sprache leer ist, d.h. wir können mir der Grammatik, die die Sprache erzeugt keine Wörter erzeugen. Achtung: jede leere Sprache ist regulär.
Endlichkeit: ob die Sprache endlich ist (endliche Sprache = reguläre Sprache = endlicher Automat)
Universalität: ob die Sprache alle Kombinationen der Elemente aus dem Alphabet $\Sigma$ umfasst
Eindeutigkeit: ob es für ein Wort nur einen Ableitungsbaum gibt.
Determiniertheit: es gibt einen deterministischen Kellerautomaten, der entscheidet ob $\omega$ zur Sprache gehört oder nicht.

Antwort zum Lernziel:

	kontextfrei	deterministisch
Wortproblem	+	+
Inklusion	–	–
Äquivalenz	–	+
Leerheit	+	+
Endlichkeit	+	+
Universalität	–	+
Eindeutigkeit	–	+
Determiniertheit	–	+

Damit haben wir auch die letzte Kurseinheit durch. Hoffentlich konntet Ihr etwas mit den Zusammenfassungen anfangen und es haben sich keine Fehler eingeschlichen. Wenn doch: ab damit in die Kommentare!