Uebung 4, Aufgabe 1
Uebung 4, Aufgabe 1
Wir haben hier gerade ein Problem. Was tut das die Menge aus Tupeln \(\{(a,b)\}^+\) in der Definition von \(L=\{w\in \Sigma^* | \exists w'\in\{(a,b)\}^+.w=aw'b \}\)?
Sind damit Woerter gemeint? Also nach Skript Modul 4, Seite 7.
Danke.
Sind damit Woerter gemeint? Also nach Skript Modul 4, Seite 7.
Danke.
Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)
(Decimus Iunius Iuvenalis, Satirae VI)
Re: Uebung 4, Aufgabe 1
ugs: w fängt mit "a" an, dann eine beliebige anzahl (außer 0) an "ab", abschließend "b".
also zB: w = aabb oder w = aababb
so hab ich das verstanden, keine garantie auf Korrektheit^^
wobei ich gerade selber an meiner Lösung zweifel
also zB: w = aabb oder w = aababb
so hab ich das verstanden, keine garantie auf Korrektheit^^
wobei ich gerade selber an meiner Lösung zweifel

EiSE Tutor WS 12/13
Re: Uebung 4, Aufgabe 1
So haben wir es auch verstanden. Sind uns allerdings auch überhaupt nicht sicher 
Vielen Dank aber für Deine Antwort. Dann sind wir also schonmal nicht alleine mit der Meinung

Vielen Dank aber für Deine Antwort. Dann sind wir also schonmal nicht alleine mit der Meinung

Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)
(Decimus Iunius Iuvenalis, Satirae VI)
-
- Mausschubser
- Beiträge: 49
- Registriert: 28. Sep 2009 11:39
Re: Uebung 4, Aufgabe 1
Ich halte mind. einmal "ab" auch für die naheliegendste Interpretation, auch wenn die formal glaube ich auch nicht einwandfrei ist:
So hätte man z.b. als Wort \((a,(a,b),b)\), was explizit geklammert \((a,((a,b),b))\) ist. Allerdings wäre das wort \((a,a,b,b)\) explizit geklammert \((a,(a,(b,b)))\), also nicht das selbe. Würde man die Definition also exakt lesen enthielte das Wort (a,b)-Tupel als einzelne Buchstaben, oder sehe ich das falsch? Wenn nein, ist das so gewollt?
So hätte man z.b. als Wort \((a,(a,b),b)\), was explizit geklammert \((a,((a,b),b))\) ist. Allerdings wäre das wort \((a,a,b,b)\) explizit geklammert \((a,(a,(b,b)))\), also nicht das selbe. Würde man die Definition also exakt lesen enthielte das Wort (a,b)-Tupel als einzelne Buchstaben, oder sehe ich das falsch? Wenn nein, ist das so gewollt?
Re: Uebung 4, Aufgabe 1
All of you are right. What jack_90 and hm wrote is, actually, how one should understand the task: one basically was expected to ignore the brackets. However, the criticism from DanielSchoepe is completely fair. I attempted to react to his message in the version 1.2 of the exercise which is online now.
-- Dr. Artem Starostin
Re: Uebung 4, Aufgabe 1
Thanks!
Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)
(Decimus Iunius Iuvenalis, Satirae VI)
Re: Uebung 4, Aufgabe 1
Hallo,
kann leider nicht verstehen wie kommt man zu der Antwort auf die reguläre Grammatik (aus MuLö "... Die Grammatik G spezifiziert {}, also nicht L.").
Kann mir jemand helfen?
Ist das richtig:
- In DFA und NDFA müssen aller Wörte aus L akzeptiert werden, können aber andere Wörte, die nicht zu L gehören akzeptiert werden;
- In Ausdruck und Grammatik müssen NUR Wörter aus L abgeleitet werden können
?
Danke
kann leider nicht verstehen wie kommt man zu der Antwort auf die reguläre Grammatik (aus MuLö "... Die Grammatik G spezifiziert {}, also nicht L.").
Kann mir jemand helfen?
Ist das richtig:
- In DFA und NDFA müssen aller Wörte aus L akzeptiert werden, können aber andere Wörte, die nicht zu L gehören akzeptiert werden;
- In Ausdruck und Grammatik müssen NUR Wörter aus L abgeleitet werden können
?
Danke
Re: Uebung 4, Aufgabe 1
Das liegt daran, dass die Grammatik nie terminiert. In jeder Produktionsregel befindet sich ein X0 oder X1, sodass die Wörter nie zum Ende kommen können. Somit kann kein einziges Wort abgeleitet werden, daher {}.Timbuktu hat geschrieben: kann leider nicht verstehen wie kommt man zu der Antwort auf die reguläre Grammatik (aus MuLö "... Die Grammatik G spezifiziert {}, also nicht L.").
Bei Ausdruck und Grammatik hast du Recht, sie müssen genau die Wörter aus L ableiten. Nicht mehr und nicht weniger. Mit den Automaten ist es genauso. Auch sie müssen alle Wörter aus L akzeptieren und keine anderen.Timbuktu hat geschrieben: - In DFA und NDFA müssen aller Wörte aus L akzeptiert werden, können aber andere Wörte, die nicht zu L gehören akzeptiert werden;
- In Ausdruck und Grammatik müssen NUR Wörter aus L abgeleitet werden können
Ich hoffe, ich konnte dir helfen

Re: Uebung 4, Aufgabe 1
Nein, ein Automat darf nicht noch zusätzlich weitere Wörter akzeptieren, weil die sonst automatisch mit in die Sprache des Automaten kämen, und damit würde nicht mehr die geforderte Sprache erkannt werden, sondern eine andere (nämlich eine größere).
Die Grammatik G spezifiziert die leere Sprache. Man kann also keine Wörter damit ableiten. Das liegt daran, dass nur ableitbare Wörter ohne Variablen in die Sprache einer Grammatik aufgenommen werden. Du kannst aber leicht sehen, dass bei dieser Grammatik in jedem abgeleiteten Wort immer genau eine Variable drin ist, du kommst also nie auf ein "fertig abgeleitetes" Wort, auf das man keine Produktionen mehr anwenden kann.
Die Grammatik G spezifiziert die leere Sprache. Man kann also keine Wörter damit ableiten. Das liegt daran, dass nur ableitbare Wörter ohne Variablen in die Sprache einer Grammatik aufgenommen werden. Du kannst aber leicht sehen, dass bei dieser Grammatik in jedem abgeleiteten Wort immer genau eine Variable drin ist, du kommst also nie auf ein "fertig abgeleitetes" Wort, auf das man keine Produktionen mehr anwenden kann.
Re: Uebung 4, Aufgabe 1
Alles klar! Viel Dank.
Damit die Ableitungen nach einer Grammatik terminieren können müssen X->e oder X->a (a von Alphabet) in der Produktionsregel auftreten?
Damit die Ableitungen nach einer Grammatik terminieren können müssen X->e oder X->a (a von Alphabet) in der Produktionsregel auftreten?
Re: Uebung 4, Aufgabe 1
Genau
Es darf in mindestens einer Regel keine Variable mehr vorkommen, damit die Ableitung terminieren kann. Mindestens eine Regel darf also nur aus den Terminalsymbolen bestehen, welche meistens das Alphabet und epsilon sind.
