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

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
134 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!

in HU-2-3 von uafjv uafjv Tutor(in) (168k Punkte)  

5 Antworten

0 Pluspunkte 0 Minuspunkte

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?

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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
0 0
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ß
0 0
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 Pluspunkte 0 Minuspunkte

Hallo,

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

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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 Pluspunkte 0 Minuspunkte

Hey,

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

S -> aSa | A,

A -> aAb | Λ.

Vielen Dank

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hallo,

ja, du darfst die Grammatik so schreiben.

Grüße

Antonio

(Tutor)
0 Pluspunkte 0 Minuspunkte

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!

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
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 :)
0 0
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.
0 0
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 Pluspunkte 0 Minuspunkte

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!

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Soweit ich sehe, erzeugt deine Grammatik die selbe Sprache und ist damit richtig.

Gruß,

Tobias
...