Betrachten Sie die Menge L={w element {a,b}* | g(w)=h(w)}, wobei die Homomorphismen g, h: {a,b)* -> {a,b}* durch g(a):=lambda
g(b):=a: h(a):= a: h(b):=a erklaert sind.

Ist diese Menge regulaer? Eigentlich schon oder? Wie beweis ich das?

Wenn sie regulär ist, musst du das doch gar nicht beweisen, sondenr nur einen richtigen rationalen Ausdruck hinschreiben. Beweisen musst du nur, wenn du meinst, sie ist nicht regulär.

soll heissen wenn ich einen rationalen ausdruck angeben kann ist sie regulaer? in diesem fall b* oder?

sehe ich genauso
(b)*

Wenn sie regulär ist, musst du das doch gar nicht beweisen, sondenr nur einen richtigen rationalen Ausdruck hinschreiben. Beweisen musst du nur, wenn du meinst, sie ist nicht regulär.

Ich habe nichts mit der Übunug zu tun, aber vermutlich wird man auch noch eine kleine Begründung abliefern müssen, warum der RA korrekt ist, oder?

harrrr, aber welche? hab mir die musterloesungen der vergangenen jahre mal gezogen aber daraus werd ich auch nicht schlau

beweis:
sei L1 = b*

für alle w e L1 gilt g(w) = h(w) -> w e L
für alle w e {a,b}*\L1 gilt g(w) != h(w) -> w !e L

-> L1 = L

das könnte man doch recht einfach zeigen,
klingt dann gleich viel überzeugender

Also zu 7.2.1 habe ich folgendes gelesen (in einem schlauen Buch!):

Ein Homomorphismus ist eine Funktion von Zeichenreihen, die bewirkt, dass jedes Symbold durch eine bestimmte Zeichenreihe ersezt wird.

Also wenn man für g(w) = a^n Eingaben im Automaten hat/macht, dann erhält man immer Lambda (Lambda^n = lambda), bei h(w) = a^n erhält man a^n.
Wenn man nun für g(w) = b^n Eingaben im Automaten macht, dann erhält man a^n, bei h(b) erhält man dann bei der selben Eingabe auch a^n.

Wenn L eine reguläre Sprache über dem Albhapet {a,b} ist und g, h Homomorphismen über {a,b} sind, dann ist auch g,h(L) regulär.

Also 7.2(i) ist ja nur regulär, wenn g(w)=h(w) gilt (oder?)! Bei Eingaben von einem oder mehreren b ist das ja der Fall aber bei Eingaben von a nicht, also müßte die Menge nicht regulär sein oder reicht es, wenn man einen regulären Ausdruck angeben kann wie oben bewiesen?

LG Frischling

Also zu 7.2.1 habe ich folgendes gelesen (in einem schlauen Buch!):

Ein Homomorphismus ist eine Funktion von Zeichenreihen, die bewirkt, dass jedes Symbold durch eine bestimmte Zeichenreihe ersezt wird.

Also wenn man für g(w) = a^n Eingaben im Automaten hat/macht, dann erhält man immer Lambda (Lambda^n = lambda), bei h(w) = a^n erhält man a^n.
Wenn man nun für g(w) = b^n Eingaben im Automaten macht, dann erhält man a^n, bei h(b) erhält man dann bei der selben Eingabe auch a^n.

besser:
g(a^n) = lambda, h(a^n) = a^n
g(b^n) = a^n, h(b^n) = a^n

Wenn L eine reguläre Sprache über dem Albhapet {a,b} ist und g, h Homomorphismen über {a,b} sind, dann ist auch g,h(L) regulär.

Also 7.2(i) ist ja nur regulär, wenn g(w)=h(w) gilt (oder?)!

g(w)=h(w) gilt auf jeden fall für alle wörter w aus der sprache,
so ist sie ja definiert..,
jetzt ist nur noch die frage, welche wörter in der sprache drin sind,

Bei Eingaben von einem oder mehreren b ist das ja der Fall aber bei Eingaben von a nicht

daraus kann man folgern, das die sprache keine wörter enthält, die ein a enthalten,
nicht aber, dass die sprache nicht regulär ist

Ja aber (Skript S. 52) reguläre Mengen sind die Mengen von Wörtern, die von einem DFA akzeptiert werden.

Und wir haben dóch mit L(A) oder L_sonst was die zu akzeptierende Sprache eines Automaten beschrieben (bis jetzt jedenfalls).

Mein Gedanke war, wenn das ganze nun regulär sein soll, dann müßte doch g(w)=h(w) erfüllt werden und das auch durch die Homomorphismen g(a), g(b), h(a) und h(b) oder sehe ich das falsch????

Reicht es, dass der Automat nur Eingaben von b akzeptiert? Denn a werden durch L_7.2(i) ja nicht akzeptiert:

g(a^2) = lambda ist ungleich h(a2^)=aa
wird also von L-7.2(i) nicht akzeptiert.

LG Frischling

Ja aber (Skript S. 52) reguläre Mengen sind die Mengen von Wörtern, die von einem DFA akzeptiert werden.

ja

Und wir haben dóch mit L(A) oder L_sonst was die zu akzeptierende Sprache eines Automaten beschrieben (bis jetzt jedenfalls).

ja

Mein Gedanke war, wenn das ganze nun regulär sein soll, dann müßte doch g(w)=h(w) erfüllt werden und das auch durch die Homomorphismen g(a), g(b), h(a) und h(b) oder sehe ich das falsch????

versteh ich nicht [img]http://www.fb18.de/gfx/3.gif[/img]

eine beliebige menge L kann auch regulär sein,
ohne dass g(w) = h(w) gelten muss (beispiel L = {a} ist regulär)

g(a), g(b), h(a) und h(b) sind keine homomorphismen sondern wörter

Reicht es, dass der Automat nur Eingaben von b akzeptiert? Denn a werden durch L_7.2(i) ja nicht akzeptiert:

g(a^2) = lambda ist ungleich h(a2^)=aa
wird also von L-7.2(i) nicht akzeptiert.

LG Frischling

die sprache ist (b)* ,
und ein automat zu dieser sprache akzeptiert logischerweise nur b's, ja

Hmm, Verständigungs- oder/und Verständnisproblem meinerseits:

In der Aufgabe ist L_7.2(i) := {w € {a,b}^*| g(w) = h(w)}

Das heißt also das der Automat von L_7.2(i) z.B. das Wort aaaa nicht akzeptiert, da ja g(a^4)=Lambda und h(a^4)=aaaa ist und somit g(a^4) undgleich h(a^4) ist.

Warum ist die Menge trotzdem noch regulär?
Meine Frage vorher war, der Automat ist über das Alphapet {a,b}^* definiert, aber ich kann ja a nun überhaupt nicht benutzen, da so ein Wort nicht akzeptiert wird!?

Noch ein Beispiel: w = abbba => g(a^1 b^3 a^1) = bbb
=> h(a^1 b^3 a^1) = abbba

g(a^1 b^3 a^1) = bbb ist ungleich h(a^1 b^3 a^1) = abbba
das Wort abbba wird nicht von L_7.2(i) akzeptiert.

Wenn eine reguläre Menge = der Menge der Wörter, die ein Automat akzeptiert wird:

1) Ist das nicht über das ganze Alphabet relevant? (also
Schei** auf a)

2) Keine Ahnung - stilstand im Hirn!!!

LG Frischling

Hmm, Verständigungs- oder/und Verständnisproblem meinerseits:

In der Aufgabe ist L_7.2(i) := {w € {a,b}^*| g(w) = h(w)}

Das heißt also das der Automat von L_7.2(i) z.B. das Wort aaaa nicht akzeptiert, da ja g(a^4)=Lambda und h(a^4)=aaaa ist und somit g(a^4) undgleich h(a^4) ist.

ja

Warum ist die Menge trotzdem noch regulär?

b* (= die menge) ist doch einwandfrei regulär, was spricht dagegen?

aaaa ist nicht dabei, na und?

Meine Frage vorher war, der Automat ist über das Alphapet {a,b}^* definiert, aber ich kann ja a nun überhaupt nicht benutzen, da so ein Wort nicht akzeptiert wird!?

Noch ein Beispiel: w = abbba => g(a^1 b^3 a^1) = bbb
=> h(a^1 b^3 a^1) = abbba

g(a^1 b^3 a^1) = bbb ist ungleich h(a^1 b^3 a^1) = abbba
das Wort abbba wird nicht von L_7.2(i) akzeptiert.

die menge enthält kein wort, das a enthält, richtig

Wenn eine reguläre Menge = der Menge der Wörter, die ein Automat akzeptiert wird:

1) Ist das nicht über das ganze Alphabet relevant? (also
Schei** auf a)

2) Keine Ahnung - stilstand im Hirn!!!

versteh ich immer noch nicht ;)

wie kann irgendwas 'über das ganze alphabet relevant' sein?

was hat das damit zu tun, das eine reguläre menge eine menge ist,
für die ein sie akzeptierender automat existiert?

Gut, ich nehme das mal so hin. Also es ist egal, ob nun ein Automat über eine Alphabet definiert (damit meine ich w € {a,b}^*, weiß ich wie man das sonst nennt) ist, wenn ein a in diesem Fall nicht akzeptiert wird ist das halt so, aber der Automat ist hat dann trotzdem eine reguläre Sprache!