Wie zeige ich, ob das Komplement einer regulären Sprache ebenfalls eine reg. Sprache ist?

Diskutiere Wie zeige ich, ob das Komplement einer regulären Sprache ebenfalls eine reg. Sprache ist? im Mathematik Forum; Ich hab eine kurze Frage: Eine Eigenschaft der Klasse der regulären Sprachen ist doch, dass wenn eine Sprache L regulär ist, dass dann auch das...

  1. Rock45
    Rock45 Mitglied
    Ich hab eine kurze Frage: Eine Eigenschaft der Klasse der regulären Sprachen ist doch, dass wenn eine Sprache L regulär ist, dass dann auch das Komplement regulär ist.

    Entwerfe ich also einen Automaten, der L akzeptiert, habe ich damit gezeigt, dass das Komplement ebenfalls regulär ist oder denke ich da falsch?
     
  2. Vielleicht hilft dir dieser Java-Kurs hier weiter --> (hier klicken)
  3. JCODA
    JCODA Aktives Mitglied
    Damit hast du die Regularität von L "benutzt".
    Was kannst du nun mit diesem Automaten tun, damit er das Komplement akzeptiert?
     
  4. Rock45
    Rock45 Mitglied
    Die Frage ist ja: Muss ich denn noch was mit dem Automaten tun?

    Ein Beweis wäre doch: Sei D ein deterministischer endlicher Automat, der L erkennt. Der Automat D erreicht für jedes Wort w [​IMG] L einen Endzustand und für jedes Wort w nicht Element L einen Nicht-Endzustand. Indem in D alle Endzustände zu Nicht-Endzuständen gemacht werden und umgekehrt, entsteht ein deterministischer endlicher Automat D-Komplement, der L-Komplement erkennt. Also ist L-Komplement regulär.

    Die Frage ist also: Reicht es einen Automaten für L zu haben, um zu zeigen, dass L regulär ist und dann darauf zu verweisen, dass eine Eigenschaft der Klasse der regulären Sprachen ist, dass auch das Komplement regulär ist, oder ist der reine Automat zu wenig?
     
  5. JCODA
    JCODA Aktives Mitglied
    Das hast du ja getan:
    Das reicht.

    Aber bemerke, du hast nicht "nichts" getan, sondern du hast genau das richtige gemacht, was nötig ist :)
     
  6. Rock45
    Rock45 Mitglied
    Danke nochmal...aber du verwirrst mich...:)
    Die Frage war ja, ob der Automat als solches reicht, mit der Erklärung, dass die Klasse der reg. Sprachen die Abschlusseigenschaft hat.

    Der Beweis, den ich angeführt habe, wäre also nicht in der Lösung enthalten. Nur Automat D für Sprache L und der Verweis, dass aus der Tatsache, dass L regulär ist folgt, dass auch L-Komplement regulär ist.

    Würde das in deinen Augen reichen oder nicht?
     
  7. JCODA
    JCODA Aktives Mitglied
    Oh, entschuldige, ich hab' nicht genau genug gelesen.

    Also du redest von "Eigenschaft der Klasse der regulären Sprachen ist, dass auch das Komplement regulär ist", aber diese Aussage ist nicht gottgegeben. Die versuchst du ja gerade zu beweisen.

    Oder verstehe ich dich nun falsch? ^^
     
  8. Rock45
    Rock45 Mitglied
    Nein. DAS verstehst du nun richtig. :) Okay...dann reicht das nicht. Ich dachte einfach, dass ich davon ausgehen kann, weil das "allgemein gültig" sei.
     
Die Seite wird geladen...

Wie zeige ich, ob das Komplement einer regulären Sprache ebenfalls eine reg. Sprache ist? - Ähnliche Themen

ArrayListe in einer JComboBox anzeigen
ArrayListe in einer JComboBox anzeigen im Forum Java Basics - Anfänger-Themen
Dateien im Ordner anzeigen
Dateien im Ordner anzeigen im Forum Java Basics - Anfänger-Themen
Bilder/Grafiken (zb: ".jpg") gestaucht zu Anzeige bringen
Bilder/Grafiken (zb: ".jpg") gestaucht zu Anzeige bringen im Forum Allgemeine Java-Themen
Stringanzeige in einem Label
Stringanzeige in einem Label im Forum Java Basics - Anfänger-Themen
GUI-Bedienelemente mit Zeiger/Referenzen-Array veralten
GUI-Bedienelemente mit Zeiger/Referenzen-Array veralten im Forum Java Basics - Anfänger-Themen
Thema: Wie zeige ich, ob das Komplement einer regulären Sprache ebenfalls eine reg. Sprache ist?