Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

–1 Punkt
116 Aufrufe

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!

Gefragt 21, Sep 2015 in HU-2-3 von uafjv uafjv Tutor(in) (167,990 Punkte)  

5 Antworten

0 Punkte

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?

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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
0 Punkte

Hallo,

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

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
0 Punkte

Hey,

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

S -> aSa | A,

A -> aAb | Λ.

Vielen Dank

 

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Hallo,

ja, du darfst die Grammatik so schreiben.

Grüße

Antonio

(Tutor)
0 Punkte

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!

 

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
0 Punkte

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!

 

Beantwortet 21, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Soweit ich sehe, erzeugt deine Grammatik die selbe Sprache und ist damit richtig.

Gruß,

Tobias
...