Theoretische Informatik

Satz:  Seien L₀ und L₁ reguläre Sprachen über einem Alphabet A. Dann sind die Vereinigung L = L₀ ∪ L₁, die Verkettung L = L₀L₁ und der Abschluss L = L₀* wiederum reguläre Sprachen.

Beweis:  Seien X₀ und X₁ die regulären Ausdrücke, die L₀ bzw. L₁ erzeugen. Dann erzeugt der reguläre Ausdruck X₀ | X₁ die Sprache L = L₀ ∪ L₁, der reguläre Ausdruck X₀X₁ die Sprache L = L₀L₁ und der reguläre Ausdruck X₀* die Sprache L = L₀*. Also ist die jeweilige erzeugte Sprache L regulär.

Satz:  Sei L eine reguläre Sprache über einem Alphabet A. Dann ist das Komplement L = A* \ L wiederum eine reguläre Sprache.

Beweis:  Sei D ein deterministischer endlicher Automat, der L erkennt. Der Automat D erreicht für jedes Wort w ∈ L einen Endzustand und für jedes Wort w ∉ L einen Nicht-Endzustand. Indem in D alle Endzustände zu Nicht-Endzuständen gemacht werden und umgekehrt, entsteht ein deterministischer endlicher Automat D, der L erkennt. Also ist L regulär.

Beispiel:  Der folgende deterministische endliche Automat (Bild 1a) erkennt die Sprache aller Wörter über {a, b}, die mit a anfangen und mit a aufhören. Der andere deterministische endliche Automat (Bild 1b) erkennt das Komplement dieser Sprache, also alle Wörter, die mit b anfangen oder mit b aufhören sowie das leere Wort.

Satz:  Seien L₀ und L₁ reguläre Sprachen über einem Alphabet A. Dann ist der Durchschnitt L = L₀ ∩ L₁ wiederum eine reguläre Sprache.

Beweis:  Für die Sprachen L₀ und L₁ gilt nach der Regel von De Morgan

Da durch Vereinigung und Komplement­bildung wiederum reguläre Sprachen entstehen, ist auch der Durchschnitt regulär.

Definition:  Das Spiegelbild eines Wortes x = x₀ ... x_n-1 ist das Wort

x^R  =  x_n-1 ... x₀,

also das Wort x rückwärts gelesen. Das Spiegelbild einer Sprache L ist die Sprache

L^R  =  { x^R  |  x ∈ L },

also die Menge der gespiegelten Wörter von L.

Satz:  Sei L eine reguläre Sprache. Dann ist das Spiegelbild L^R wiederum eine reguläre Sprache.

Beweis:  Siehe Aufgabe 2.

Aufgabe 1:  Im Beweis des Satzes, dass das Komplement einer regulären Sprache wieder regulär ist, wird ein deterministischer endlicher Automat verwendet. Geben Sie ein möglichst einfaches Beispiel dafür an, dass der Beweis im Allgemeinen nicht funktioniert, wenn der endliche Automat nicht deterministisch ist.

Aufgabe 2:  Zeigen Sie: Das Spiegelbild einer regulären Sprache ist regulär.