Theoretische Informatik

Mächtigkeiten der Mengen aller Wörter bzw. aller Sprachen über einem Alphabet

 aufwärts

Ein Alphabet A ist eine nichtleere, endliche Menge von Zeichen. Ein Wort über A ist eine endliche Folge von Zeichen aus A. Die Menge aller Wörter über A wird mit A* bezeichnet. Eine Sprache über A ist eine Teilmenge von A*.

Mächtigkeit der Menge aller Wörter über A

Satz:  Sei A ein Alphabet. Es gibt abzählbar unendlich viele Wörter über A, d.h. die Menge A* aller Wörter über A hat die Mächtigkeit abzählbar unendlich:

| A* |  =  ℵ0

Beweis:  Angenommen, die Menge A* wäre endlich. Dann enthält A* ein Wort w maximaler Länge (A* ist nicht leer, denn A* enthält zumindest das leere Wort ε). Sei a ein Zeichen aus dem Alphabet A (das Alphabet A ist nicht leer). Dann ist wa ein Wort über A, d.h. wa Element A*, aber andererseits wa nicht Element A*, da A* nur Wörter der Länge kleiner gleich|w| enthält und |wa| > |w| gilt. Dies ist ein Widerspruch; also ist die Annahme falsch.

A* enthält also unendlich viele Elemente, selbst dann, wenn das Alphabet A nur aus einem einzigen Zeichen besteht.

Um zu zeigen, dass A* abzählbar unendlich viele Wörter enthält, benötigen wir eine bijektive Abbildung zwischen A* und natürliche Zahlen. Hierzu definieren wir eine Ordnung auf A; anschließend ordnen wir die Wörter von A* zunächst ihrer Länge nach und dann bei gleicher Länge lexiko­graphisch (wie im Lexikon) unter Zugrunde­legung der Ordnung von A. Diese Ordnung auf A* wird als längen-lexiko­graphische Ordnung bezeichnet. Die bijektive Abbildung zwischen A* und natürliche Zahlen ergibt sich, indem jedes Wort von A* auf die Position abgebildet wird, in der es in der längen-lexiko­graphischen Ordnung auftritt.

Beispiel:  Sei A = {a, b, c} das Alphabet. Die Ordnung auf A sei a < b < c. Dann lassen sich die Wörter von A* gemäß der längen-lexiko­graphischen Ordnung wie folgt anordnen und abzählen:

 

12345678910111213141516...
εabcaaabacbabbbccacbccaaaaabaac...

Mächtigkeit der Menge aller Sprachen über A

Eine Sprache über einem Alphabet A ist eine beliebige Menge von Wörtern, also eine Teilmenge von A*. Wie viele solche Teilmengen, also wie viele Sprachen gibt es?

Offenbar ist die Menge A aller Sprachen über dem Alphabet A gleich der Menge aller Teilmengen von A*, also der Potenzmenge von A*:

A  =  Potenzmenge(A*)

Stets ist es so, dass die Potenzmenge Potenzmenge(M) einer beliebigen Menge M eine größere Mächtigkeit hat als M. Die Menge A* aller Wörter über A ist abzählbar unendlich, daher ist die Potenzmenge Potenzmenge(A*) über­abzählbar unendlich. Wir zeigen dies im Folgenden noch einmal explizit.

Satz:  Sei A ein Alphabet. Es gibt über­abzählbar unendlich viele Sprachen über A, d.h. die Mächtigkeit der Menge aller Sprachen über A ist über­abzählbar unendlich.

Der Satz lässt sich mit dem 2. Cantorschen Diagonal­verfahren beweisen (nach G. Cantorzur Person).

Beweis:  

Angenommen, die Menge aller Sprachen über A wäre abzählbar. Dann lassen sich die Sprachen als L1, L2, L3, ... abzählen und in folgendes Schema eintragen:

w1w2w3w4w5w6...
 L1 111011...
L2101010...
L3011001...
 drei Punkte übereinander  drei Punkte diagonal 

 

Die Spalten des Schemas sind mit den Wörtern von A* über­schrieben, beispiels­weise in längen-lexiko­graphischer Anordnung. Jede Zeile i enthält die charakteristische Funktion der Sprache Li bezüglich A*, d.h. in der mit wj über­schriebenen Spalte steht eine 1, wenn wj Element Li gilt und 0 sonst. Beispiels­weise enthält L2 die Wörter w1, w3, w5, ...

Wir betrachten nun die Diagonale des Schemas (hellgelbe Felder). Die dort befindlichen Felder enthalten die charakteristische Funktion der Diagonal­sprache Ld. Die Sprache Ld enthält hier die Wörter w1, w3, ...

Das Komplement Ld der Diagonal­sprache Ld ist nun eine Sprache, die in diesem Schema nicht vorkommen kann. Denn Ld kann keines der Li sein, weil Ld definitions­gemäß in der i-ten Spalte des Schemas genau dann eine 0 hat, wenn Li dort eine 1 hat, und umgekehrt.

Wir hatten angenommen, dass wir alle Sprachen in das Schema eingetragen haben und finden nun eine Sprache, die nicht in dem Schema auftritt. Dies ist ein Widerspruch. Daher kann die Menge aller Sprachen nicht abzählbar sein.

Sprachen mit endlicher Beschreibung

Es gibt also über­abzählbar viele, also sehr, sehr viele Sprachen. Die meisten dieser Sprachen allerdings lassen sich gar nicht explizit angeben, weil sie keine endliche Beschreibung besitzen.

Eine endliche Beschreibung einer Sprache ist beispiels­weise ein regulärer Ausdruck oder eine Grammatik oder auch eine informelle Beschreibung in Textform. Aber alle diese endlichen Beschreibungen sind endliche Zeichen­folgen, also Wörter, über einem zugrunde­liegenden Alphabet.

Es gibt aber nur abzählbar viele Wörter über einem Alphabet. Also gibt es auch nur abzählbar viele endliche Beschreibungen. Also gibt es auch nur abzählbar viele Sprachen, die eine endliche Beschreibung besitzen. Dies sind, gegenüber der über­wältigend großen Menge aller Sprachen, die wenigsten.

 

Weiter mit:   [Reguläre Sprachen]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 26.09.2010   Updated: 13.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik