Theoretische Informatik - Aufgaben

Abgeschlossenheit der regulären Sprachen

 aufwärts

Aufgabe:  

  1. Das Komplement L einer Sprache L enthalten in 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 L1 Durchschnitt L2 zweier regulärer Sprachen L1 und L2 ü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 LR 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 { anbn | n Element natürliche Zahlen0 } nicht regulär ist.

 

 

 

up

 

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