3. Aufgabe zur Abgeschlossenheit

Aufgabe zur Abgeschlossenheit

  • V

    Aufgabe:

    Die Operation

    min:P(Σ⋆)→P(Σ⋆)min: \mathbb P\left(\Sigma^{\star}\right) \to \mathbb P\left(\Sigma^{\star}\right)

    sei definiert durch

    min(L)={w∈L∣∀u,v∈Σ⋆ mit w=uv,1≤∣u∣,∣v∣≥1:u∉L}min(L)=\{ w \in L | \forall u,v \in \Sigma^{\star} \text{ mit } w=uv, 1 \leq |u|, |v| \geq 1: u \notin L \}

    min beinhaltet also alle diejenigen Wörter aus L, deren echten Präfixe nicht in L liegen. Sei nun L eine reguläre Sprache, ist dann auch min(L) regulär?

    Begründen Sie Ihre Antwort.

    Edit zur Aufgabe: Ich weiß, dass in der Sprachdefinition der Aufgabe ein Fehler vorliegt, der die Aufgabe eigentlich unsinnig macht. Dieser steht auch genauso auf meinem Blatt. Da aber die Erklärung der Sprache auch auf dem Übungszettel draufsteht ist die eigentliche Sprachdefinition "ja eh" überflüssig. Das ist übrigens der (fast) 🙂 genau Wortlaut meines Dozenten!

    Meine Lösung:

    In meinem Lehrbuch (der Hopcroft) steht, dass, wenn L eine reguläre Sprache über dem Alphabt Σ\Sigma ist, dann ist L‾=Σ⋆−L\overline{L} = \Sigma^{\star} - L auch eine reguläre Sprache.

    1. Frage: Warum ist das so? Ich hab mir das so zusammengereimt, weil die Differenz zweier regulärer Sprachen regulär ist. Stimmt das? So steht's zumindestens im besagten Lehrbuch...

    Weiter in der Lösung:

    Da nun eben min(L) genau die Wörter akzeptiert, welche nicht in L liegen, trifft doch dann genau dieser Satz zu, und ich darf hiermit Begründen: min(L)=L‾=Σ⋆−Lmin(L) = \overline{L} = \Sigma^{\star} - L.

    Somit wäre doch min(L)=L‾min(L) = \overline{L} regulär.

    Stimmen meine Überlegungen?

    0
  • M

    vip@r schrieb:

    In meinem Lehrbuch (der Hopcroft) steht, dass, wenn L eine reguläre Sprache über dem Alphabt Σ\Sigma ist, dann ist L‾=Σ⋆−L\overline{L} = \Sigma^{\star} - L auch eine reguläre Sprache.

    1. Frage: Warum ist das so? Ich hab mir das so zusammengereimt, weil die Differenz zweier regulärer Sprachen regulär ist. Stimmt das? So steht's zumindestens im besagten Lehrbuch...

    Wenn Letzteres bekannt ist, dann ja.

    Da nun eben min(L) genau die Wörter akzeptiert

    Akzeptiert? min(L) ist eine Menge, die kann nichts akzeptieren.

    welche nicht in L liegen, trifft doch dann genau dieser Satz zu, und ich darf hiermit Begründen: min(L)=L‾=Σ⋆−Lmin(L) = \overline{L} = \Sigma^{\star} - L.

    min(L) ist Teilmenge von L. Keine Ahnung, wie du auf das Komplement kommst.

    Edit: Für die Aufgabe reichen folgende Beobachtungen:
    Das Komplement regulärer Sprachen ist regulär.
    Die Konkatenation regulärer Sprachen ist regulär.

    Edit 2: Was ist denn der Fehler in der Definition? Ich sehe ihn nicht.

    0
  • C

    vip@r schrieb:

    1. Frage: Warum ist das so? Ich hab mir das so zusammengereimt, weil die Differenz zweier regulärer Sprachen regulär ist. Stimmt das? So steht's zumindestens im besagten Lehrbuch...

    Und warum ist die Differenz zweier regulärer Sprachen regulär? Das verschiebt das Problem doch nur.

    Nur falls es nicht klar wurde: Diese Frage kannst du selber beantworten, indem du in besagtem Lehrbuch liest. Das steht dort nämlich drin.

    0
  • K

    Da nun eben min(L) genau die Wörter akzeptiert, welche nicht in L liegen

    Falsch!

    Btw. mache deine Hausaufgaben doch mal alleine oder bezahle jemanden dafuer. Kann ja nicht angehen, dass du jede Woche deine Hausaufgaben hier loesen laesst.

    Selber denken, Glueck verschenken.

    0
  • V

    Michael E. schrieb:

    Da nun eben min(L) genau die Wörter akzeptiert

    Akzeptiert? min(L) ist eine Menge, die kann nichts akzeptieren.

    Oh, das muss natürlich beinhalten heißen.

    Michael E. schrieb:

    Edit: Für die Aufgabe reichen folgende Beobachtungen:
    Das Komplement regulärer Sprachen ist regulär.
    Die Konkatenation regulärer Sprachen ist regulär.

    Dass das Komplement regulär ist, weiß ich durch das Lehrbuch. Dass die Konkatenation regulär ist weiß ich ebenfalls durch das Lehrbuch. Aber wie helfen mir nun diese beiden Erkenntnisse in Bezug auf die Lösung weiter?

    Aussage von meinem Lehrbuch ist ja: "Wenn L eine reguläre Sprache über dem Alphabt Σ ist, dann ist L‾=Σ⋆−L\overline{L} = \Sigma^{\star}-L auch eine reguläre Sprache.

    Die Aufgabe sagt ir, dass L eine reguläre Sprache ist. Also muss doch L‾=Σ⋆−L\overline{L} = \Sigma^{\star}-L die Lösung sein, da ja der besagte Satz aus dem Lehrbuch greift. Du sagst aber, dass man Komplement (das hätt ich hier ja verwendet) UND die Konkatenation benötigt. Ich verstehe aber nicht, wo ich hier noch zusätzlich die Konkatenation benötige...

    0
  • M

    0
  • M

    Sorry, hatte mich verlesen. Schau dir doch mal die Nerode-Relation von min(L) an.

    0
  • O

    vip@r schrieb:

    Die Aufgabe sagt ir, dass L eine reguläre Sprache ist. Also muss doch L‾=Σ⋆−L\overline{L} = \Sigma^{\star}-L die Lösung sein

    Warum? was hat das mit min(L) zu tun? Min(l) betrifft Wörter von denen die ersten n Zeichen wiederum kein Wort aus L ergeben.

    Beispiel:
    L={0n1m |m>0,n>0}

    Dann ist 00011111 in L
    aber der Präfix 000 nicht
    trotzdem liegt es nicht in min(L) da es nicht für alle Präfixe gilt: 0001 ist in L => 00011111 nicht in min(L)

    anderes Beispiel
    L={"ab", "cd", "ef", "cdef"}
    min(L)={"ab","cd", "ef"}
    aber nicht "cdef", da "cd" in L liegt.

    Das ist die Sprache die du untersuchen sollst.

    Auch von mir: versuche bitte in Zukunft von selbst auf die Lösung zu kommen. Der erste Schritt ist wie immer, die Aufgabestellung zu verstehen und sich zum Beispiel mit einem kleinen Beispiel zu veranschaulichen.

    0
  • V

    Muss ich für die Aufgabe wissen, wie die Sprachdefinition von L heißt? Gegeben ist ja nur die Sprachdefinition von min(L)...

    0
  • K

    Sie ist regulaer, mehr ist nicht noetig.

    0
Anmelden zum Antworten