Die Sprache hallihallo

Lösung geprüft

Die Aufgabe der heutigen Stunde ist die Sprache hallihallo! Hier wird es zum ersten Mal richtig formal: aus ein paar Beispielwörtern soll eine allgemeine Regel werden, und am Ende steht eine Mengenschreibweise mit Exponent. Das sieht nach Mathe aus, ist aber nur konsequent aufgeschrieben, was man sowieso sieht.

Die Aufgabenstellung lautet

Zur Sprache L_hallihallo gehören zum Beispiel die folgenden Wörter:
hallo hallihallo hallihallihallo hallihallihallihallo …

Aufgabe 1: Muster erkennen. a) Markiere in den vier angegebenen Wörtern den Teil, der wiederholt wird, und den Teil, mit dem jedes Wort endet. b) Gib die nächsten zwei Wörter der Sprache an. c) Beschreibe die Bildungsregel der Sprache in eigenen Worten.

Aufgabe 2: Alphabet und Sprachzugehörigkeit. a) Bestimme ein möglichst kleines Alphabet Σ, über dem alle oben angegebenen Wörter gebildet werden können. b) Entscheide für jedes Wort, ob es ein Wort über Σ ist und ob es zur Sprache gehört. Begründe mindestens zwei Entscheidungen.

Aufgabe 3: Die Sprache formal beschreiben. a) Ergänze die Tabelle. b) Vervollständige die Mengenschreibweise. c) Erkläre, warum die Sprache unendlich viele Wörter enthält, obwohl das Alphabet nur endlich viele Zeichen besitzt.

Aufgabe 4: Zwei Modellierungen vergleichen. A steht für halli, B steht für hallo, Σ₂ = {A, B}. a) Gib die ersten vier Wörter der codierten Sprache über Σ₂ an. b) Beschreibe die codierte Sprache mit A, B und einer Variablen n. c) Vergleiche die beiden Modellierungen. Welche Beschreibung macht die Struktur der Sprache deutlicher?

Aufgabe 1 – Das Muster

a) Wiederholter Teil und Ende

            hallo          ->                      hallo
       halli hallo         ->  halli               hallo
 halli halli hallo         ->  halli halli         hallo
 halli halli halli hallo   ->  halli halli halli   hallo
 ^^^^^^^^^^^^^^^^^^^^         wiederholter Teil    Ende

Wiederholt wird halli, und jedes Wort endet auf hallo. Die Ähnlichkeit der beiden macht die Aufgabe kniffliger als sie ist – sie unterscheiden sich nur im letzten Buchstaben.

b) Die nächsten zwei Wörter

hallihallihallihallihallo
hallihallihallihallihallihallo

c) Die Bildungsregel

Ein „halli" kann kein Mal oder beliebig oft vorkommen, und es endet immer mit einem „hallo". Dadurch können unendlich viele Wörter gebildet werden.

Der Punkt, den man dabei leicht übersieht: kein Mal ist auch erlaubt. Deshalb gehört das einzelne „hallo" zur Sprache, obwohl gar kein „halli" davorsteht.

stateDiagram-v2
    direction LR
    [*] --> Anfang
    Anfang : Anfang
    Fertig : Wort fertig
    Anfang --> Anfang : halli (beliebig oft, auch kein Mal)
    Anfang --> Fertig : hallo (genau einmal, am Ende)
    Fertig --> [*]

Wie ein Wort der Sprache hallihallo entsteht

Die Schleife ist der ganze Trick: man darf beliebig oft „halli" nehmen – auch null Mal – und muss die Schleife mit einem „hallo" verlassen. Danach ist das Wort zu Ende, ein zweites „hallo" gibt es nicht.

Aufgabe 2 – Alphabet und Zugehörigkeit

a) Das kleinste Alphabet

Σ = { halli, hallo }

Gefragt ist ein möglichst kleines Alphabet. Man könnte auch die einzelnen Buchstaben nehmen – {h, a, l, i, o} – und damit ließen sich die Wörter ebenfalls bilden. Nur werden dann auch tausende sinnlose Folgen wie „iiiaal" möglich, und das Muster verschwindet.

Nimmt man die beiden Bausteine als unteilbare Zeichen, beschreibt das Alphabet die Struktur der Sprache schon mit. Das ist derselbe Gedanke wie beim Backofen, wo das Umluft-Symbol ein Zeichen war und nicht in Striche zerlegt wurde.

b) Die Tabelle

Wort	w ∈ Σ*	w ∈ L_hallihallo	Begründung
`hallo`	ja	ja	„hallo" kann aus dem Alphabet gebildet werden und ist gültig, wenn es ganz am Anfang steht, wo noch kein „halli" vorkommt.
`hallihallihallo`	ja	ja	Zwei „halli", danach ein „hallo" am Ende – die Regel ist erfüllt.
`hallihalli`	ja	nein	„hallihalli" kann nicht zur Sprache gehören, da kein „hallo" am Ende des Strings liegt und die Syntax somit invalide ist.
`hallohalli`	ja	nein	Beide Bausteine sind im Alphabet, aber in der falschen Reihenfolge. Das „hallo" muss am Ende stehen, nicht am Anfang.
`hello`	nein	nein	„hello" ist nicht Teil des Alphabetes. Es lässt sich aus „halli" und „hallo" gar nicht zusammensetzen.

Der Unterschied zwischen den beiden Spalten

Die beiden Fragen werden gerne verwechselt, sind aber verschieden:

Frage	Bedeutung
w ∈ Σ*	Lässt sich das Wort überhaupt aus den Zeichen des Alphabets zusammensetzen? Σ* ist die Menge aller Zeichenfolgen über Σ, ohne jede Regel.
w ∈ L	Hält das Wort zusätzlich die Regeln der Sprache ein?

Bei hallihalli und hallohalli sieht man den Unterschied am deutlichsten: beide sind aus den Zeichen des Alphabets gebaut, also in Σ*, verstoßen aber gegen die Bildungsregel und sind deshalb nicht in L. L ist immer eine Teilmenge von Σ*.

Aufgabe 3 – Die formale Beschreibung

a) Die Tabelle

n	(halli)ⁿ	(halli)ⁿ hallo
0	ε	hallo
1	halli	hallihallo
2	hallihalli	hallihallihallo
3	hallihallihalli	hallihallihallihallo

Das ε (epsilon) ist das leere Wort – ein Wort aus null Zeichen. Es ist nicht dasselbe wie „nichts": ε ist ein gültiges Wort, es hat nur die Länge 0. Deshalb steht bei n = 0 in der dritten Spalte trotzdem „hallo" und nicht etwa nichts.

b) Die Mengenschreibweise

L = { (halli)ⁿ hallo | n ∈ ℕ₀ }

Gelesen: „Die Menge aller Wörter der Form n-mal halli gefolgt von hallo, wobei n eine natürliche Zahl einschließlich der Null ist."

Das ₀ bei ℕ₀ ist entscheidend und kein Schönheitsfehler. Ohne es wäre das einzelne „hallo" nicht in der Sprache, obwohl es in der Aufgabenstellung ausdrücklich als Beispiel steht. Wer hier nur ℕ schreibt, hat eine andere Sprache beschrieben.

c) Warum unendlich viele Wörter

Das Alphabet hat nur zwei Zeichen, die Sprache aber unendlich viele Wörter. Das ist kein Widerspruch: die Zeichen sind begrenzt, die Wortlänge nicht.

Für jedes n ∈ ℕ₀ gibt es genau ein Wort, und es gibt unendlich viele natürliche Zahlen. Zu jedem Wort kann man ein weiteres „halli" davorsetzen und bekommt ein neues, längeres – das hört nie auf. Ein längstes Wort gibt es also nicht.

Dasselbe gilt übrigens für Java: das Alphabet ist endlich (alle Zeichen der Tastatur), und trotzdem gibt es unendlich viele mögliche Programme.

Aufgabe 4 – Die zweite Modellierung

a) Die ersten vier Wörter über Σ₂

B      AB      AAB      AAAB

b) Die codierte Sprache

L₂ = { Aⁿ B | n ∈ ℕ₀ }

c) Welche Modellierung ist besser?

„aⁿ + b" ist meiner Meinung nach die bessere Modellierung, da sie Übersichtlichkeit erlaubt.

	Σ = {halli, hallo}	Σ₂ = {A, B}
Wort bei n = 3	`hallihallihallihallo`	`AAAB`
Struktur erkennbar?	schlecht – man muss zählen und aufpassen, wo „halli" aufhört	sofort
Verwechslungsgefahr	hoch, „halli" und „hallo" unterscheiden sich in einem Buchstaben	keine
Bezug zur Wirklichkeit	man sieht, worum es geht	verloren – A und B sagen für sich nichts

Bei AAAB sieht man die Struktur auf einen Blick, bei hallihallihallihallo muss man Silben zählen. Und das ist genau der Zweck einer Modellierung: das Wesentliche sichtbar machen und den Rest weglassen.

Der Preis dafür ist, dass die Bedeutung verschwindet – aus A und B kann man nicht mehr ablesen, dass es mal um Begrüßungen ging. Für die Untersuchung der Struktur ist das aber egal, und genau darum geht es hier.

Nebenbei: { Aⁿ B | n ∈ ℕ₀ } ist eine der bekanntesten Beispielsprachen der theoretischen Informatik. Man trifft sie später bei Automaten und Grammatiken immer wieder.