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 das kostenlose Training 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.
     
  9. Schau dir jetzt hier den Kurs an und lerne Java zu programmieren: --> Hier klicken, um mehr zu erfahren (Klick)
Die Seite wird geladen...

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

Design-Anzeige im Windowbuilder
Design-Anzeige im Windowbuilder im Forum AWT, Swing, JavaFX & SWT
Anzeige Fehler auf anderem Gerät
Anzeige Fehler auf anderem Gerät im Forum Java Basics - Anfänger-Themen
Jdialog nur 1x anzeigen
Jdialog nur 1x anzeigen im Forum Java Basics - Anfänger-Themen
Ping in JTextArea anzeigen
Ping in JTextArea anzeigen im Forum Netzwerkprogrammierung
Anzeigefehler bei JTree
Anzeigefehler bei JTree im Forum AWT, Swing, JavaFX & SWT
Thema: Wie zeige ich, ob das Komplement einer regulären Sprache ebenfalls eine reg. Sprache ist?