[FoSAP] Ableitungsrelation

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

Ableitungsrelation

Beitragvon 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
My software never has bugs. It just develops random features.
Benutzeravatar
Coolcat
Promoter
 
Beiträge: 2574
Registriert: 28.11.05 21:26
Wohnort: Kohlscheid / Düsseldorf
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon 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)
Benutzeravatar
nomawie
 
Beiträge: 181
Registriert: 20.01.06 19:53
Wohnort: Aachen

Beitragvon 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}
My software never has bugs. It just develops random features.
Benutzeravatar
Coolcat
Promoter
 
Beiträge: 2574
Registriert: 28.11.05 21:26
Wohnort: Kohlscheid / Düsseldorf
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon 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...
xero
 
Beiträge: 225
Registriert: 23.09.05 13:58

Beitragvon 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
Frag' mich nicht, ich putz' hier nur...
Benutzeravatar
p0llux
Matt Eicheln
 
Beiträge: 841
Registriert: 07.12.05 17:03
Wohnort: Aachen

Beitragvon 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...
"The (Toyota) Prius is so slow - the child could run on the street, retrieve the ball... and grow to puberty before actually hit it."
[J. Clarkson - TopGear]
Benutzeravatar
Lück
 
Beiträge: 70
Registriert: 04.12.05 20:23
Wohnort: Soest

Beitragvon 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
My software never has bugs. It just develops random features.
Benutzeravatar
Coolcat
Promoter
 
Beiträge: 2574
Registriert: 28.11.05 21:26
Wohnort: Kohlscheid / Düsseldorf
Studiengang: Informatik (Dipl.)
Studiert seit: fertig
Anwendungsfach: BWL

Beitragvon 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:
"The (Toyota) Prius is so slow - the child could run on the street, retrieve the ball... and grow to puberty before actually hit it."
[J. Clarkson - TopGear]
Benutzeravatar
Lück
 
Beiträge: 70
Registriert: 04.12.05 20:23
Wohnort: Soest

Re: Ableitungsrelation

Beitragvon 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 :-)
kanita
 
Beiträge: 1
Registriert: 22.12.14 14:25
Studiengang: Informatik (Dipl.)
Studiert seit: SS 10
Anwendungsfach: BWL


Zurück zu Theoretische Informatik