Habt ihr Tipps oder Ansätze für diese Aufgabe???
bist du nich ein kleines bisschen zu spät dran?
wie wärs mit:
ich habe eine reguläre sprache R, die durch einen automaten (x, x, x, x, x) beschrieben wird.
ich habe eine reguläre sprache U, die durch einen automaten (x, x, x, x, x) beschrieben wird.
jetzt konstruiere ich einen automaten A, der die sprache R/U akzeptiert.
damit ist jede sprache die durch mengensubtraktion aus zwei regulären sprachen entsteht auch eine reguläre sprache.
versuchs erstmal mit zwei konkreten regulären sprachen/automaten. dann hast du eine idee davon was zu tun ist und kannst das vorgehen verallgemeinern.
R \ U kann man auch mit den anderen Mengenoperationen ausdrücken
Ferner ist schon bekannt, dass unter der Vereinigung und Komplement
die Klasse Reg abgeschlossen ist.
Also drückt man R \ U nur mit Vereinigung und Komplement aus => R\ U abgeschlossen.
Mit dem wissen aus DM sollte das kein Problem sein ^^
Ich hatte mir das so überlegt:
Wenn R eine reguläre Sprache ist, gibt es einen Automaten, der alle Worte aus R akzeptiert.
Daraus folgt, daß er auch alle Worte einer beliebigen Teilmenge von R akzeptiert; die Teilmengen von R sind also sämtlich auch reguläre Sprachen.
R \U ist eine Teilmenge von R, also auch reguläre Sprache.
Ist das brauchbar?
Gruß,
Stefan
Nein, denn dann waeren ja alle Wortmengen regulaer. Schliesslich sind ja alle Wortmengen Teilmenge von [latex]\Sigma^*[/latex].
Daraus folgt, daß er auch alle Worte einer beliebigen Teilmenge von R akzeptiert; die Teilmengen von R sind also sämtlich auch reguläre Sprachen.
Damit eine Sprache regulär ist, muss es einen Automaten geben, der
genaudie Wörter der Sprache akzeptiert. Der Automat für R akzeptiert aber eben
mehr Wörter als nur die in R\U, also kannst du den nicht für R\U verwenden.
Es ist im allgemeinen
nicht so, dass eine Sprache, die weniger Wörter enthält
(z.B. eine Teilmenge ist), auch einfacher ist. Die Komplexität einer Sprache hängt
eben auch entscheidend davon ab, welche Wörter
nicht in der Menge enthalten
sind. Wie UncleOwen schon gesagt hat: eine der einfachsten Sprachen, die man
kennt ([latex]\Sigma^*[/latex]) enthält sogar jede andere Sprache über dem Alphabet [latex]\Sigma[/latex].
Mist, aber danke für die Erklärung…