Theoretische Informatik - Aufgaben

Aufgabe:  

1. Das Komplement L einer Sprache L ⊆ A* ist die Sprache A* \ L. Zeigen Sie: Das Komplement einer regulären Sprache L ist eine reguläre Sprache.

   Hinweis: Formen Sie den deterministischen endlichen Automaten D, der L erkennt, in einen deterministischen endlichen Automaten D' um, der L erkennt.

    

2. Zeigen Sie: Der Durchschnitt L₁ ∩ L₂ zweier regulärer Sprachen L₁ und L₂ über einem Alphabet A ist eine reguläre Sprache.

   Hinweis: Wir wissen, dass die Vereinigung zweier regulärer Sprachen eine reguläre Sprache ist. Drücken Sie den Durchschnitt mit Hilfe von Vereinigung und Komplement aus (Regel von de Morgan).

    

3. Das Spiegelbild L^R einer Sprache L ist die Menge der Wörter von L jeweils rückwärts gelesen.

   Zeigen Sie: Das Spiegelbild einer regulären Sprache L ist eine reguläre Sprache.

    

    

   Wozu sind diese Überlegungen von Nutzen? Zum Beispiel hierfür:

    

4. Benutzen Sie die Aussage von b. und zeigen Sie: Die Sprache

   L  =  { w | w enthält gleich viele a's und b's }

   über dem Alphabet {a, b} ist nicht regulär.

   Hinweis: Wir wissen, dass { aⁿbⁿ | n ∈ ℕ₀ } nicht regulär ist.