Uebung 4, Aufgabe 1

Benutzeravatar
hm
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 26. Okt 2004 23:51
Wohnort: DA

Uebung 4, Aufgabe 1

Beitrag von hm »

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.
Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)

jack_90
Mausschubser
Mausschubser
Beiträge: 75
Registriert: 29. Sep 2009 22:38
Wohnort: Darmstadt
Kontaktdaten:

Re: Uebung 4, Aufgabe 1

Beitrag von jack_90 »

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 :oops:
EiSE Tutor WS 12/13

Benutzeravatar
hm
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 26. Okt 2004 23:51
Wohnort: DA

Re: Uebung 4, Aufgabe 1

Beitrag von hm »

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 ;)
Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)

DanielSchoepe
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 28. Sep 2009 11:39

Re: Uebung 4, Aufgabe 1

Beitrag von DanielSchoepe »

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?

Benutzeravatar
starostin
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 8. Jul 2010 12:45

Re: Uebung 4, Aufgabe 1

Beitrag von starostin »

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

Benutzeravatar
hm
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 26. Okt 2004 23:51
Wohnort: DA

Re: Uebung 4, Aufgabe 1

Beitrag von hm »

Thanks!
Quis custodiet ipsos custodes?
(Decimus Iunius Iuvenalis, Satirae VI)

Timbuktu
Erstie
Erstie
Beiträge: 15
Registriert: 24. Okt 2010 15:25

Re: Uebung 4, Aufgabe 1

Beitrag von Timbuktu »

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

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Uebung 4, Aufgabe 1

Beitrag von Iniii »

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.").
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: - 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
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.

Ich hoffe, ich konnte dir helfen :)

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Uebung 4, Aufgabe 1

Beitrag von dschneid »

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.

Timbuktu
Erstie
Erstie
Beiträge: 15
Registriert: 24. Okt 2010 15:25

Re: Uebung 4, Aufgabe 1

Beitrag von Timbuktu »

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?

Iniii
Neuling
Neuling
Beiträge: 9
Registriert: 17. Jun 2009 22:14

Re: Uebung 4, Aufgabe 1

Beitrag von Iniii »

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.

Antworten

Zurück zu „Archiv“