reguläre Sprache und Präfixe



  • Hi Leute!

    Ich hab folgende Aufgabe zu machen mit der ich leider überhaupt nicht zu Rande komme und hoffe deshalb auf etwas Hilfe von euch 🙂

    Hier die Aufgabe:

    Die Operation min: P(Σ^) -> P(Σ^) sei definiert durch

    min(L) = {w \in L | \forall u,v \in Σ^* mit w=uv, 1≤|u|, |v|≥1: u \notin L}

    min beinhaltet also alle diejenigen Wörter aus L, deren echte 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.

    Sorry, aber das LaTeX hab ich hier nicht zum Laufen gebracht!

    Könnt ihr mir trotzdem helfen?



  • vielleicht wenn du einen Ansatz bringst, was du schon hast (Ideen?)

    Die Komplettlösung ohne einen Beitrag von dir wirst du hier wohl nicht bekommen.



  • Komplettlösung will ich ja auch gar nicht. Mein Ansatz:

    Laut Aufgabe weiß man ja, dass die Sprache L regulär ist. Weiter heißt es: "min(L) beinhaltet also alle diejenigen Wörter aus L, deren echte Präfixe nicht in L liegen."

    Also ist doch quasi min(L) eine Teilmenge der Sprache L welche ja regulär ist. Somit sollte doch min(L) auch regulär sein, da sie nur aus der Sprache von L stammen kann welche ja regulär ist...

    Das ist soweit mal mein Ansatz; ich weiß is nicht gerade viel...



  • vip@r schrieb:

    Also ist doch quasi min(L) eine Teilmenge der Sprache L welche ja regulär ist. Somit sollte doch min(L) auch regulär sein, da sie nur aus der Sprache von L stammen kann welche ja regulär ist...

    Dir ist hoffentlich klar, daß eine Teilmenge einer regulären Sprache nicht unbedingt selber regulär sein muß (jede Sprache ist eine Teilmenge des regulären Σ*).



  • Ok, nein das war mir bisher nicht klar. Jetzt aber. Die Frage bleibt aber dennoch; wie geht's weiter?



  • Nur ein Gedanke, den du eventuell noch formaler ausarbeiten mußt:
    Du kannst dir den DFA für die gegebene Sprache nehmen und alle Kanten von einem akzeptierenden Zustand kappen (bzw. auf einen Fehler-Zustand umbiegen). Dann akzeptiert der neue Automat nur Wörter der ursprünglichen Sprache, bei denen kein Präfix akzeptiert wurde.



  • Wie konstruiert man sich denn am besten einen Automaten auf's Papier wenn eine Sprache, hier min(L), gegeben ist?

    Kannst du mir das sagen?

    So, wie ich das verstehe, setzt sich das Wort w der Sprache min(L) ja aus u und v zusammen, wobei u und v jeweils größergleich 1 sein müssen wobei aber u (also das Präfix) nicht in der Sprache L sein darf. Stimmt das soweit? Wann fällt aber das Präfix also u aus der Sprache L raus? Ich verstehe das so, es fällt raus wenn die Teilwortlänge von u nicht mehr stimmt. Das heißt die Teilwortlänge vom Präfix u mus also kleiner 1 sein, was ja dann 0 wäre und es somit dann gar nicht mehr existiert... Stimmt's soweit?



  • Tipp1: wenn du probleme mit allen Aufgaben deines Arbeitsblattes hast, dann solltest du dir eine Lerngruppe suchen.

    Tipp2: durchscuh nochmal deine Unterlagen ob du davon irgendwas verwenden kannst. In der Klausur musst du das auch alleine hin kriegen.

    //edit ich habe irgendwie das Gefühl, dass die Lösung folgendes ist:

    Sei A der Automat der L erkennt.
    Sei B der Automat A bei dem alle Zustände (außer dem Fehlerzustand) akzeptierend sind.

    Dann ist B geschnitten negiert(A) der gesuchte Automat.

    Ohne Beweis.


Anmelden zum Antworten