infostudium.de

von **Coolcat** » 10.04.06 21:02

Kann mir jemand sagen wann man nun --> und wann => schreibt?

Ich hatte das so verstanden, dass --> benutzt wird, wenn das komplette Wort durch eine Regel ersetzt wird. Dementsprechend => wenn nur ein Teilwort ersetzt wird. Dabei kann man dann => aber auch einfach immer benutzen.

Jetzt habe ich hier eine Vorlesungsmitschrift vor mir (war am Freitag in der zeitgleichen Diffnumvorlesung :roll:

), in der --> scheinbar nach gutdünken benutzt wird.

Beispiel aus dem Beweis der Sprache L(G) = {a^n b^n c^n | n > 0} :

...
a^{i-1} a B b^{i+1} c^{i+1} -->
a^{i-1} aaA b^{i+1} c^{i+1} -->
a^{i+1} bA b^i c^{i+1} =>*
a^{i+1} b^{i+1} A c^{i+1}
...

Was ist richtig?

Coolcat

von **nomawie** » 10.04.06 21:57

hab leider die erste vorlesung wegen softwarepraktikum verpasst als das definiert wurde, aber eigentlich müsste es so sein, dass --> verwendet wird wenn man genau eine ableitungsregel anwendet und ==> wenn man durch Ableitungsregeln dahinkommt (können also mehrere Ableitungen sein)

von **Coolcat** » 10.04.06 22:06

Ähm, und was ist dann =>* ?

Definition:

x,y $\in (V \cup \Sigma)*$ dann gilt x => y
gdw. $\exists$ u,v,w,z $\in (V \cup \Sigma)*$ so dass x = wuz, y=wvz, u --> v

x =>* y bezeichnet die reflexive, transitive Hülle von x.
$\underbrace{x \Rightarrow x_1 \Rightarrow x_2 \Rightarrow \ldots \Rightarrow x_n \Rightarrow y }_{x \Rightarrow * y}$

von **xero** » 10.04.06 22:07

also ich hab mir an einer Stelle ne kleine Notiz bei dem Doppelpfeil gemacht und da hab ich stehen "Doppelpfeil(=>) weil innerhalb von einem Kontext". kA ob es hilft, werd mich erst morgen mit ATFS auseinandersetzen...

von **p0llux** » 10.04.06 23:22

=>* ist die reflexive, transistive hülle von =>

Wenn ich das korrekt verstanden habe, dann bedeutet "A =>* B" nicht mehr als, das man B aus A erzeugen kann indem man endlich viele Produktionsregeln anwendet...

Das mit dem Kontext beim => ist ja das aus der definition mit dem "Teilwörter" ersetzen. Allerdings ist bei der Definition als einleitendes und abschliessenden wort was um das durch eine produktionsregel ersetzte gerät drumliegt nicht das leere Worte ausgeschlossen. Also sollte immer => nicht falsch sein... Aber kein plan... Morgen mal Lück fragen.

Gruß,
Michael

von **Lück** » 11.04.06 10:16

p0llux hat geschrieben:=>* ist die reflexive, transistive hülle von =>

Wenn ich das korrekt verstanden habe, dann bedeutet "A =>* B" nicht mehr als, das man B aus A erzeugen kann indem man endlich viele Produktionsregeln anwendet...

Das mit dem Kontext beim => ist ja das aus der definition mit dem "Teilwörter" ersetzen. Allerdings ist bei der Definition als einleitendes und abschliessenden wort was um das durch eine produktionsregel ersetzte gerät drumliegt nicht das leere Worte ausgeschlossen. Also sollte immer => nicht falsch sein... Aber kein plan... Morgen mal Lück fragen.

So ist es:

=>* ist die reflexive, transitive Hülle von =>, also das Anwenden von endlich vielen (auch verschiedenen! und auch keinen!) Ableitungsschritten.

Der Einfachpfeil ( ---> ) war wohl nur ein syntaktischer Fehler in der Vorlesung und nicht einmal dem Assistenten in diesem Zusammenhang bekannt.

Zusammenfassend:

Für Ableitungen nur => oder =>* bzw. andere notationelle Abwandlungen des => -Pfeils (z.B. für Links- bzw. Rechtsableitungen etc. pp.).

EDIT: Dreckfuhler beseitigt...

von **Coolcat** » 11.04.06 19:36

Also ich habe jetzt eben im Tutorium gefragt:
Dort wurde mir zunächst gesagt es müsse alles mit dem --> Pfeil gemacht werden. Nachdem ich dann sagte was du (Lück) hier gesagt hast, hieß es dann "kA".

Coolcat

von **Lück** » 11.04.06 20:45

Coolcat hat geschrieben:Also ich habe jetzt eben im Tutorium gefragt:
Dort wurde mir zunächst gesagt es müsse alles mit dem --> Pfeil gemacht werden. Nachdem ich dann sagte was du (Lück) hier gesagt hast, hieß es dann "kA".
Coolcat

Also ich war mir zunächst auch nicht definitiv sicher, ob --> eine besondere Bedeutung in der Katoen-Vorlesung erhalten hatte. Aber da der Henrik Bohnenkamp mit mir übereinstimmte und die Notation "=> , =>*" als "normal" bezeichnete, war ich beruhigt und fühlte mich bestätigt. Er meinte, daß da im Anschrieb bei der Vorlesung was durcheinander gelaufen sein muss.

Es würd mich auch wundern, wenn "-->" ein Ableitungspfeil darstellt, da "-->" bereits für die Seitentrennung in den Produktionen verwendet wird. Das sind zwei Dinge, die man besser nicht durcheinanderschmeisst. Schlimm genug, daß die eindeutige Indermark'sche Notation mit den geschwungenen Folgepfeilen nicht fortgesetzt wird. :wink:

von **kanita** » 22.12.14 14:29

Gibt es denn irgendwo die Lösungen zur ersten Übung? Die habe ich nämlich leider nicht mitbekommen. Es wäre nett, wenn jemand einen Link hat oder die Beweisskizzen von 1.2 und 1.4 hier posten könnte :-)

infostudium.de

Forum zum Informatikstudium an der RWTH Aachen

[FoSAP] Ableitungsrelation

Ableitungsrelation

Re: Ableitungsrelation