Übersicht alternativer Lösungsvorschläge aus dem alten ILIAS-Forum

Question

Dieser Post wurde der Übersichtlichkeit halber erstellt, um die alternativen Lösungsvorschläge aus dem alten ILIAS-Forum nicht überzubetonen. Wenn Sie neue alternative Lösungsvorschläge diskutieren wollen, sollten Sie eine neue Frage erstellen - und NICHT hier posten!

Answer 1

Hallo,

in Teil b wird steht diese Produktion:

S -> A;
A -> aAa|B;
B -> aBb|lambda;

Allerdings impliziert eine kontextfreie Grammatik doch, dass das leere Wort zwar in der Produktion enthalten sein, jedoch nicht erzeugt werden darf.

Angenommen ich wähle hier: S->A->B->lambda kann ich das leere Wort erzeugen. Wie kann das sein? Wo ist mein Fehler?

Comments

Hallo,

dein Automat stimmt nicht ganz. Dein Übergang (s1,a,a)->(s1,lambda) sollte eigentlich in s2 wechseln, sonst könntest du das Wort aaabab erzeugen. Sonst passt es aber (weil kein Determinismus gefordert ist).

Gruß,

Adam

---

Hallo Adam,

danke für die Antwort. Allerdings glaube ich, dass deine Begründung nicht richtig ist. Ein Wort bei dem ein a auf ein b folgt ist nicht erzeugbar, da es keine Übergänge von b auf a gibt. Da müsste es ja sowas geben wie (s?,a,b) -> ... und das gibts es nicht.

Gruß

---

Hallo,

Adam hat hier völlig recht, Sie schreiben das b ja nicht in den Keller, demnach brauchen Sie auch keinen Übergang von (s?, a, b). Das würde ja bedeuten, dass Sie davor ein b in den Keller geschrieben haben. Da Sie das abe rnicht machen, brauchen Sie einen solchen Übergang nicht. Sie müssen deswegen in s2 wechseln, um zu gewährleisten, dass sie die vorgegebene Reihenfolge der a's und b's einhalten. Also zuerst b's und dann a's. Würden Sie das nicht machen, könnten Sie in s1 in eine beliebigen Reihenfolge b's und a's lesen.

Sie verwechseln das wohl mit der monotonen Grammatik. Die Produktionsform für kontextfreie Regeln lautet: N x (N vereinigt T)*, also eine Abbildung auf lambda ist auch möglich.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König

Answer 2

Hallo,

ich wollte fragen, ob bei der L5 folgende Grammatik erlaubt ist.

Comments

Hallo,

diese Grammatk ist leider nicht ganz korrekt, weil du das Nonterminal B willkürlich auf die Terminalsymbole a und b ableiten könntest und so die Struktur des Wortes nicht gleich bleibt. Man könnte bei deiner Grammatik beispielsweise das Wort aaabab ableiten, was aber nicht Teil der vorgegebenen Sprache L5 wäre.

Viele Grüße

Johannes (Tutor)

Answer 3

Hey,

darf ich bei b) die Grammatik auch folgendermaßen schreiben:

S -> aSa | A,

A -> aAb | Λ.

Vielen Dank

 

Comments

Hallo,

ja, du darfst die Grammatik so schreiben.

Grüße

Antonio

(Tutor)

Answer 4

Hallo, ich wollte nur kurz fragen - ist auch folgender KA richtig?

(S0, lambda, k0) -> (Se, k0)
(S0, a, k0) -> (S0, ak0)

(S0, a, a) -> (S0, aa) | (s2, lambda)
(S0, b, a) -> (S1, lambda)
(S1, b, a) -> (S1, lambda) | (S2, lambda)

(S2, a, a) -> (S2, lambda)

(S1, lambda, k0) -> (Se, k0)
(S2, lambda, k0) -> (Se, k0)

Gruß & Dank!

 

Comments

Entspricht soweit ich sehe der Lösung von Pete mit Adams Korrektur (s.o.) und ist daher richtig (falls Se einziger Endzustand ist).

Tobias (Tutor)

PS: Wenn du den Aufgabenteil dazuschreibst und die vorherigen Posts ließt, spart das dem Antwortenden Arbeit :)

---

Danke Tobias, was die Grammatik von Petes unterscheidet, sind die | (also entweder-oder Anweisungen), zumindest soweit ich da durchgeblickt habe. Deswegen habe ich gefragt. Danke dir.

---

Die | werden nur bei Grammatiken benutzt, nicht bei nichtdeterministischen Kellerautomaten.

Bitte verwende stets die Notation, die in der Vorlesung vorgestellt wurde. Selbst wenn man versteht, was du mit deiner "Privatnotation" meinst, tust du weder dir noch den an der Klausurkorrektur/-bewertung Beteiligten einen Gefallen.

Gruß,

Tobias (Tutor)

Answer 5

nochmal eine Frage zu der Grammatik bei a)

wäre folgende Grammatik auch richtig?

S -> aSb | aAb

A -> bAa | ba

Es ist doch zulässig, auch auf mehrere Terminalsymbole abzuleiten. So spare ich mir eine Zeile und ich stelle sicher, dass m und n >= 1 sind.

Danke!

 

Comments

Soweit ich sehe, erzeugt deine Grammatik die selbe Sprache und ist damit richtig.

Gruß,

Tobias