Uebung 4, Aufgabe 1

[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.

[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

[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

[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?

[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.

[hm]

Thanks!

[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]

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 {}.

- 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]

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]

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]

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.