Bin grade beim Lösen ein muster klausur, die jemand im Netz freigegeben hat und komme auf einige Probleme…

also SIGMA={a,b,c} L={lam, ab, bb, ba}

h: {a,b,c}* —-> {d,e}*
h(a)= dd, h(b) = de, h©= lambda

meine frage ist:

h^-1 (d*e*) = ???

zweitens im skript steht auf seite 85 (3.62), dass a*b* = a*(a+b*)(b*)* .

Wie kommt man da drauf ?? wie formt man das um ??.. gibt es welche Regeln und so ??

kann jemand vielleicht die wichtige Regeln von Rationale ausdrücke kurz darstellen ?? aber nicht die doofe die im Skript setehn wie a ={a} oder so was.. sondern schon komplexe formel.. ..

danke..

mfg

die 'jemand' im Netz freigegeben hat.. ;)

bei deiner ersten Frage komme ich jetzt auch ins Stutzen,
da es mit dieser Substitution ja gar nicht möglich ist, mehr als ein e hintereinander zu erzeugen,
wie soll denn da die Umkehrung funktionieren?..

notfalls halt so wie in der Lösung angegeben,
was ist denn deine Frage dazu?,

man muss natürlich die verschiedenen Fälle unterscheiden
d*e* könnte lambda, d, ddddd, ddde, e, eee, usw. sein,

da muss man schauen dass man einen Ausdruck zusammenbastelt
dessen Substitution alle diese Fälle abdeckt

—–

a*b* bedeutet beliebig viele a's hintereinander und dann beliebig viele b's hintereinander

das kann man beliebig auseinanderbauen
(wobei man wohl eher den anderen Weg sucht,
vom komplizierten Ausdruck rechts zum einfachen)

simpel ist doch die Regel a* = (a*)* oder auch a* = a*a*, a* = a*+a*

da a* = a*+a* funktioniert,
ist es ja nicht weit auf Ideen der Art a* = a* + a zu kommen

wenn man bedenkt das die linke Alternative auf der rechten Seite ja schon gleich der linken Seite ist,
dann kann man da ruhig noch einen Teil der Menge per + Verknüpfen

natürlich ohne das etwas neues hinzukommt, a* = a* + b geht nicht

auf die Reihenfolge muss man achten, a* b* = a* a* b* b*, aber nicht a* b* a* b*, das ist ja logisch

etwas tricky ist der Ausdruck den du da nennst schon,
aber irgendwie kommt man da immer hin

a* b* = a* b* + a* b*
= a* a b* + a* b* (von der linken Alternative die Menge b* abgezogen (auch das leere Wort))
= a* a b* + a* b* b*
= a* (a+b*) b*
= a* (a+b*) (b*)*





oder auch mit der Überlegung:
a* Mitte b*

was ist die Mitte damit der gesamte Ausdruck = a* b* ist?
entweder gar nix (lambda) oder beliebig viele a's und dann beliebig viele b's,
obwohl gar nicht allzu viele a's oder b's drin sein müssen,
denn links und rechts sind ja genug davon,

Hauptsache man wird nicht eingeschränkt
(etwa dass das Wort mindestens 2 a's haben muss wenn Mitte = aa)

(a+b*) erfüllt alle Ansprüche, lambda geht immer noch, ist ja in b* drin,

also a* b* = a* (a+b*) b*

so mal wieder viel blah blah,
hoffentlich kommt jetzt keiner mit einer kurzen formalen Methode ;)

da es mit dieser Substitution ja gar nicht möglich ist, mehr als ein e hintereinander zu erzeugen, wie soll denn da die Umkehrung funktionieren?..

Ist nicht nötig. Die Defintion für ein Wort w ist:

h^-1(w) = {v \in {a,b,c}* | h(v) = w}

Diese Menge kann auch leer sein - für bspw. w = ee ist sie es, da kein v exisitert mit h(v) = ee.

Für eine Sprache L wird h^-1(L) dann definiert als Vereinigung aller h^-1(w) mit w aus L.

Hier kann man sich überlegen: Die Worte mit einer geraden Anzahl an d's haben ein Urbild (hiermit sind alle Worte aus {a}* erzeugbar). Die Worte mit einer ungeraden Anzahl an d's und einem dann folgenden e haben ein Urbild (hiermit sind alle Worte aus {a}*{b} erzeugbar). Zudem können an beliebiger Stelle des Wortes beliebig viele c's stehen. Es ergibt sich dann für h^-1({d}*{e}*) gerade ({a,c}* cup {a,c}*{b}{c}*).
(Man muss sich auch noch überlegen, dass es nicht mehr Worte geben kann. Dazu bedenke man, dass wenn nach den d's zwei oder mehr e's kommen für dieses Wort h^-1(w) die leere Menge ist, ferner, dass für eine gerade Anzahl von d's und dann einem (oder mehr) e die Menge ebenfalls leer ist. Zuletzt kann nach einem e kein d mehr kommen, da dies ja nicht in d*e* wäre.)

—–
Bei dem rationalen Ausdruck a*(a+b*)(b*)* würde ich diesen in Mengenschreibweise wandeln und dann darauf rumoperieren:

{a}* ({a} cup {b}*) ({b}*)*
= {a}* ({a} cup {b}*) {b}*
= ({a}+ cup {a}*{b}*) {b}*
= {a}+{b}* cup {a}*{b}*{b}*
= {a}*{b}*

Wieder in rationalen Ausdruck a*b*.


Hoff' es hilft und ist verständlich [img]http://www.fb18.de/gfx/28.gif[/img]

Cheers,
Frank

Gerade mal die Klausurabschrift gesehen

L2 = { w element {a,b}* | wenn w ein a enthält, dann enthält w auch ein b}

Kleine Denkblockade irgendwie, wie sieht dazu der reguläre Ausdruck aus?
(b)* + ((a)*(b)°(a + b)*) ?

Hmm und noch was
R ist eine Relation in {1,2,3,4}^2
R ={(1,1), (1,2), (2,3), (2,4), (3,4), (4,1)}

(a) zeichnen sie einen graphen für den reflexiven und transitiven
abschluss R' = R* von R an

Öhh, also da bin ich total aufgeschmissen…
Geht das um die Sternbildung aus den Folien bei der Sache?

Die Antwort zu h-1(d*e*) =
lautet ({c}*{a}{c})*({lambda} \/ {b}){c}*
wenn man dem Lösungsblatt Vertrauen schenken darf, aber frag mich nicht wie man darauf kommt. Vielleicht kann sich ja auch jemand mit Durchblick der Sache nochmal widmen ^^

(b)* + ((a)*(b)°(a + b)*) ?

Kannst du machen, aber du musst es auch begründen! Die Idee könnte wie folgt skizziert werden: Wenn das Wort nur aus b's besteht ist es drinn. Wenn es mit einem b beginnt, kann danach was beliebiges folgen (das ist bei dir der zweite Fall, wobei aus a* einfach lamda genommen wird). Wenn es mit einem (oder mehreren) a beginnt, so muss irgendwann mal ein b folgen, danach wieder beliebig. Dies ist gerade durch den zweiten Fall abgedeckt. Das der rationale Ausdruck nicht mehr Worte beschreibt als die gewünschten sieht man ähnlich.

(a) zeichnen sie einen graphen für den reflexiven und transitiven abschluss R' = R* von R

Bestimme doch einfach R*. Im ersten Schritt (R^2 = R * R - wobei mit * hier die Komposition gemeint ist) kommt bspw. (1,3) hinzu (wegen (1,2) und (2,3)), sowie (1,4), (2,1), (3,1), (4,2). Einfach immer gucken: zu (1,2) passt da (2,3)? Ja. Also (1,3) hinzu. Passt (2,4)? Ja, also (1,4) hinzu. Passt (3,4)? Nein. Usw. bis sich keine Änderung mehr ergibt. Dann ist R^k (wenn k der Indize ist bei dem sich keine Änderung mehr ergibt) gleich R+. Für R* kommt dann noch Id_R hinzu (also die Paare (1,1), (2,2) usw.) und davon kannst du dann einen Graphen malen. Vgl. dazu im Skript S.13-14 und S.18.

Die Antwort zu h-1(d*e*) =
lautet ({c}*{a}{c})*({lambda} \/ {b}){c}*

Kann ich mir eigentlich nicht vorstellen, da hier kein Wort enthalten ist, dass nur aus a's besteht (bspw. nicht einmal 'a'), aber für dd ist h-1(dd) = {c}*{a}{c}*, also a in h-1(d*e*) enthalten! Evtl hast du den Sternoperator falsch gesetzt? — Im übrigen: Vertraust du meiner Lösung nicht? [img]http://www.fb18.de/gfx/22.gif[/img]

Cheers,
Frank

1. Jo danke, aber die Begründung hättest nicht schreiben müssen, da der Ausdruck Marke Eigenbau ist ^^
Wollt nur wissen, ob meine Begründung (im Geiste) irgendwo nicht hinhaut, deshalb die Frage, ob der Audruck stimmt

2. :))))
Jetzt hab ich die Aufgabe auch gepeilt, geht also nur darum die transitive und reflexive (also idR) Komponente in die Relation zu bringen, also gerichtete Kanten von der 1 zu allen anderen Ziffern die in der Relation stehen usw? Wäre jetzt so meine Idee

3.
www.slaterb.de/F1F2/probeaufgaben.zip
Nichts wäre mir ferner als majestätsbeleidigung ^^
Aber da steht die Lösung so drin. Kann natürlich sein, dasse falsch ist.

Noch was
L1 = {w element {a,b}* | w enthält doppelt so viele a's wie b's}
sei L2 = L1 geschnitten {a}* {b}*

Auch wieder {a,b}* oder ist das doch komplizierter?
Und wnen ich schneide, was passiert mit der Bedingung aus L1?
Fällt die dann unter den Tisch?

keine Sorge, ist ja nicht meine Lösung ;)
ein Stern mehr an richtiger Stelle und es scheint Azure's kürzerem Ausdruck zu entsprechen,


———

(ich nenn die 2. Menge, mit der geschnitten wird, L2)

L1 schnitt L2 = {w | w erfüllt Bedingungen von L1 und L2 (auch w e {a,b}* ist eine Bedingung)}

die Bedingung aus L1 fällt bei Schnitt nur dann unter den Tisch,
wenn L2 eine noch stärkere Bedingung hat oder sich durch den Schnitt eine stärkere Bedingung ergibt
(auf keinen Fall kann durch den Schnitt wieder {a,b}* rauskommen, also Elemente dazu..)

L2 = {w e {a,b}* | w = aab}
-> L1 schnitt L2 = L2

L2 = { w e {c}*| irgendeine Bedingung}
-> L1 schnitt L2 = {}

aber auch:

L2 = {a,b}*
-> L1 schnitt L2 = L1

in deinen Fall sagt L2 nicht viel über die Anzahl der Buchstaben aus, wohl aber über die Reihenfolge,
also gibt es einen interessanten Schnitt:

L1 schnitt L2 = {w e {a,b}* | w erfüllt Bedingungen von L1 und L2}
= {w e {a,b}* | w erhält doppelt so viele a's wie b's und die ganzen a's kommen vor den b's}
= {w e {a,b}* | w = a^2n b^n, n>= 0}

Yo vielen dank
Also werden beide Bedingungen in die Schnittmenge genommen

Was wäre denn aber wenn L1 = {a,b}* mit |a| = 2 x |b|
und L2 = {a}*{b}*{c}* | mehr c´s als b´s ?

Wenn da alle Bedingungen übernommen werden würden L1 /\ L2 = {a,b}* ||a| = 2 x |b| u. a´s vor b´s vor c´s u. mehr c´s als b´s

Die akzeptierte Sprache wäre doch dann aber gleich die leere menge, weil die Bedingung mehr c´s als b´s gar nicht erfüllt werden kann
Wäre das insoweit richtig, oder liegt da n denkfehler vor?

wäre insofern richtig, ja
da es kein Wort gibt, das in beiden Mengen vorkommt, muss der Schnitt leer sein,


deine Bedingung 'mehr c's als b's' ist etwas unformal ;),

falls auch das leere Wort lambda erlaubt ist
wäre dieses auch im Schnitt, da ja in L1 ebenfalls enthalten,

auf lambda sollte man immer extra genau schauen


edit
genauer für Schnittmenge:
L1 /\ L2 = {w e {a,b}* und w e {a}*{b}*{c}* ||a| = 2 x |b| u. a´s vor b´s vor c´s u. mehr c´s als b´s}

Na ja, da scheint das Lernen ja doch noch was zu bringen :))

{w | w = v h(v^rev) und v element {a,b,c}*}

Steht bei den Aufgaben, die du gepostet hast. Irgendwie komm ich mit dem part w = v h(v^rev) nicht so ganz klar.
Was soll das heissen?

hi,

warum kann man

{lamda, a} u {b}^+{a} = {lambda} u {b}* {a}

gleichsetzten.

Diese Gleichung ist aus der Musterlösung von 5.2 R^1(2,2).

was h ist, steht sicher dabei,
wenn es eine Substitution ist dann eben:
w besteht aus dem Wort v und der Substitution des gespiegelten Wort v dahinter


——-

{lambda,a} u {b}+ {a} ist das leere Wort, das Wort a und dann noch 'beliebig viele b's aber mindestens eins und ein a dahinter'

sieht man das Wort a als 'kein b und dahinter ein a' an,
dann kann man das doch mit 'beliebig viele b's aber mindestens eins und ein a dahinter' kombinieren zu
'beliebig viele b's (auch 0) und ein a dahinter'

-> {lambda} u {b}* {a}

noch ne frage

also wenn R^1 (2,2) ist doch ein regulärer Ausdruck wie man von Zustand "2" in den Zustand "2" gelangt und was bedeutet die 1….ausser dass es immer etwas mit der anzahl der zustände auf sich hat, sollte das dann in diesem fall bedeuten, dass mindestens ein zustand durchlaufen werden sollte?

Die Menge R^k_{i,j} enthält gerade die Wörter, die man liest um von z_i nach z_j zu gelangen, wobei als Zwischenzustände lediglich die Zustände {z_1, …, z_k} besucht werden.

D.h. wenn w \in R^k_{i,j}, so ist \delta(z_i,w) = z_j und für jedes u mit w = uv (wobei u weder das leere Wort noch w ist) gilt gerade \delta(z_i,u) = z_r mit r <= k.

Hoff' es hilft [img]http://www.fb18.de/gfx/22.gif[/img]

Cheers,
Frank

danke azure………werde damit weiterarbeiten können……

Hier kann man sich überlegen: Die Worte mit einer geraden Anzahl an d's haben ein Urbild (hiermit sind alle Worte aus {a}* erzeugbar). Die Worte mit einer ungeraden Anzahl an d's und einem dann folgenden e haben ein Urbild (hiermit sind alle Worte aus {a}*{b} erzeugbar). Zudem können an beliebiger Stelle des Wortes beliebig viele c's stehen. Es ergibt sich dann für h^-1({d}*{e}*) gerade ({a,c}* cup {a,c}*{b}{c}*).
(Man muss sich auch noch überlegen, dass es nicht mehr Worte geben kann. Dazu bedenke man, dass wenn nach den d's zwei oder mehr e's kommen für dieses Wort h^-1(w) die leere Menge ist, ferner, dass für eine gerade Anzahl von d's und dann einem (oder mehr) e die Menge ebenfalls leer ist. Zuletzt kann nach einem e kein d mehr kommen, da dies ja nicht in d*e* wäre.)


Cheers,
Frank

Hey Frank,

ich blick nicht mehr ganz durch bei der Diskussion.
Aber…

h^-1({d}*{e}*) gerade ({a,c}* cup {a,c}*{b}{c}*).

Dem stimm ich zu, wenn auch
{a}*{c}* cup {a}*{c}*{b}{c}*)
geht und Du mir erklärst, wie man auf cup kommt…


Danke.

Dem stimm ich zu, wenn auch {a}*{c}* cup {a}*{c}*{b}{c}*) geht und Du mir erklärst, wie man auf cup kommt…

Deine Lösung ähnelt meiner sehr, aber warum nimmst du {a}*{c}* statt {a,c}* (in beiden Fällen)? Dadurch ist bei dir z.B. sowas wie ca nicht enthalten! Was aber geht, da dies in der Menge h^-1(dd) ist, denn h(ca) = h©h(a) = lamda dd = dd.

Die Idee bei dem cup (Mengenvereinigung) ist oben schon skizziert. Vielleicht etwas anders: Die erste Menge beschreibt die "Urbilder" der Worte, die aus einer geraden Anzahl von d's bestehen. Die Zweite Menge die "Urbilder" der Worte, die aus einer ungeraden Anzahl von d's gefolgt von einem e bestehen.
(Andere Worte der Menge {d}*{e}* haben keine "Urbilder"!)

Hoff' es hilft [img]http://www.fb18.de/gfx/23.gif[/img]

Cheers,
Frank

wenn man jetzt für die Sprache L2 einen Kellerautomaten konstruiert der mit leerem keller akzeptiert, müsste diese automat also nur wörter erzeugen können, die jeweils eine gerade anzahl an a's und b's hat.
würde aaaabbbb akzeptiert werden aber aaabbb nicht?

L1 schnitt L2 = {w e {a,b}* | w erfüllt Bedingungen von L1 und L2}
= {w e {a,b}* | w erhält doppelt so viele a's wie b's und die ganzen a's kommen vor den b's}
= {w e {a,b}* | w = a^2n b^n, n>= 0}

Etwas gepingel: Ein Automat erzeugt keine Woerter, er akzeptiert welche!

L2 wurde hier mehrmals definiert, zuerst mit

L2 = { w element {a,b}* | wenn w ein a enthält, dann enthält w auch ein b}

Auf welches beziehst du dich? Dieser Thread wird unuebersichtlich, wenn ihr da drei-vier Themen reinschmeisst - HILFE [img]http://www.fb18.de/gfx/28.gif[/img]

Cheers,
Frank

auf dieses L2= {w e {a,b}* | w erhält doppelt so viele a's wie b's und die ganzen a's kommen vor den b's}

Die Sprache:

L2= {w e {a,b}* | w erhält doppelt so viele a's wie b's und die ganzen a's kommen vor den b's}

Deine Frage:

wenn man jetzt für die Sprache L2 einen Kellerautomaten konstruiert der mit leerem keller akzeptiert, müsste diese automat also nur wörter erzeugen können, die jeweils eine gerade anzahl an a's und b's hat. würde aaaabbbb akzeptiert werden aber aaabbb nicht?

Wenn diese Sprache kontextfrei ist (ist sie, Grammatik? <– Uebungsaufgabe [img]http://www.fb18.de/gfx/28.gif[/img]) gibt es auch einen PDA der sie mit leerem Keller akzeptiert.
Wie kommst du aber auf aaaabbbb ? Hier waere die Anzahl der a's und b's gleich?! Es sollen doch Woerter der Art a^4b^2 akzeptiert und auch a^6 b^3 (Anzahl b's ungerade).
(Also doppelte Anzahl a's wie b's.)

Hilft das schon?

Cheers,
Frank

*umpf* hatte mich verlesen und gerade drüber nachgedacht wie ich hierzu einen regulären Ausdruck formulieren würde, bis mir aufgefallen ist , dass "L2= {w e {a,b}* | w erhält doppelt so viele a's wie b's und die ganzen a's kommen vor den b's} "
ja gar keine reguläre Sprache ist und damit hierfür kein rationaler Ausdruck existiert.

Das kommt davon wenn man sich zu lange mit dem ganzen beschäftigt [img]http://www.fb18.de/gfx/wand.gif[/img]