Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in KON-AD

Beantwortet: Ableitung für c

Thu, 06 Feb 2020 11:27:45 +0000

Man soll G in Chomsky-Normalform bringen, hierfür ist erlaubt:

Von Nonterminal zu 2 Nonterminalen
Von Nonterminal zu 1 Terminal

C-->c ist von Nonterminal zu Terminal also kann man es so stehen lassen.

Bei den anderen Aufgaben die du gemacht hast waren hier vermutlich auf der rechten Seite vermutlich noch mehrere Terminale oder mehr als zwei Nonterminale wodurch die zusättliche Regel eingeführt wurde.

Siehe hierzu Tut 4...hier wird das Vorgehen erklärt.

LG, Nico (Tutor) (Alle Angaben ohne Gewähr)

Beantwortet: (b): Korrekter Eintrag in Kästchen m=3, erstes b ?

Mon, 13 Jan 2020 15:05:50 +0000

Hallo,

ja, der Eintrag ist richtig.

Um das Kästchen (m=3, 3. Spalte) zu befüllen, betrachten wir paarweise die anderen Kästchen.

1) Wir betrachten das Kästchen in de rgleichen Spalte ganz oben (m=1, 3. Spalte) und dazu das Kästchen schräg rechts über dem zu betrachtenden Kästchen (also das Kästchen mit m=2, 4. Spalte). Im einen Kästchen lesen wir (A,F) und im anderen (S, S'). Jetzt schauen wir in der Regelmenge, ob es eine Regel gibt, durch die wir auf eine der Kombinationen AS, AS', FS, FS' kommen. Diese gibt es nicht, also schauen wir die nächsten Kästchen an.

2) Jetzt betrachten wir die Kästchen (m=2, 3. Spalte) und (m=1, 5. Spalte). Hier lesen wir im ertsen Kästchen (B), und im zweiten Kästchen (B, E). Jetzt schauen wir wieder in der Regelmenge, ob es eine Regel gibt, durch die wir auf eine der Kombinationen BB oder BE kommen. Diese gibt es nicht.

Also kommt in das Kästchen (m=3, 3. Spalte) ein "-".

Ich hoffe das hilft dit weiter.

Viele Grüße,

Tim (Tutor)

A56, Chomsky-Normalfom mit λ?

Fri, 03 Feb 2017 20:45:14 +0000

Guten Abend,

mir erschließt sich leider die Verwendung des λ in der Chomsky-NF nicht. Diese ist ja schließlich unter anderem auch so definiert, dass eben jede kontextfreie Grammatik in der Chomsky-NF (und auch Greibach-NF) dargestellt werden kann, jedoch dann das λ fehlt.

Wird hier also nicht gegen die λ-Freiheit verstoßen?

Beantwortet: Schritt (4) Umbenennung doppelt

Tue, 24 Jan 2017 12:51:49 +0000

Ja, das wäre absolut auch in Ordnung!

Wenn man so einfach sagen könnte, wann das Zusammenfassen zu Problemen führen kann, würde es wahrscheinlich gar nicht mehr zu Problemen führen Solange man einen einfachen übersichtlichen Fall wie hier hat, ist es kein Problem, die Variable doppelt zu benutzen, denn man "sieht" ja, dass keine Nebeneffekte entstehen können (also Ableitungen, die man nicht haben wollte). Wird es aber komplexer, kann man leicht die Übersicht verlieren, denn die Ableitung durch Grammatiken ist ja hochgradig nichtdeterministisch. Auch bei der Implementierung eines Algorithmus für die CNF würde man normalerweise die sichere Variante wählen, denn zu entscheiden, wann eine Variable mehrfach genutzt werden kann, ist knifflig. (Wahrscheinlich gibt es dafür schon auch Regeln, die man einsehen würde, aber wir behandeln das in der Vorlesung nicht, und daher gilt einfach: Wenn Sie sich zutrauen, den Überblick zu behalten, dann komprimieren Sie die Grammatik, so weit Sie wollen, und wenn nicht, dann bleiben Sie auf der sicheren Seite.)

Beantwortet: (c) Produktion des Testwortes

Sat, 14 Jan 2017 11:10:09 +0000

Hallo,

wie du vielleicht schon gemerkt hast gibt es oft mehrere richtige Lösungen für Automaten. Das gleiche gilt natürlich auch für Grammatiken. Je nach dem in welcher Form deine Grammatik vorliegen soll, hast du jedoch manchmal mehr und manchmal weniger „Spielraum“.
Bei einer monotonen Grammatik beispielsweise könntest du z.B. statt A --> aa auch die Produktionen A--> BC , B --> a, C --> c verwenden, wodurch du eben dann „mehr Übergänge“ bräuchtest um dein Testwort aa abzuleiten.
Bei der Aufgabe hier soll die Grammatik ja in Chomsky-Normalform vorliegen, hier hast du nicht ganz so viel „Spielraum“, weil die Übergänge, welche erlaubt sind, eigentlich sehr stark vorgeschrieben sind.

Wichtig ist auch, dass allein die Produktion des Testworts nicht garantiert, dass die Grammatik richtig ist. Es müssen natürlich auch alle weiteren Wörter der Sprache abgedeckt werden und es dürfen auch keine Wörter produziert werden, die nicht Teil der Sprache sind.

Grüße, Sören (Tutor)

Beantwortet: Ausführlichkeit der Lösung

Sat, 14 Jan 2017 09:01:24 +0000

Allgemein gilt, dass Zwischenschritte nicht unbedingt notwendig sind, aber sie sind gut für Sie, weil wir so später bei der Korrektur nachvollziehen können, was Sie getan haben und eventuell noch Punkte vergeben können, obwohl das Endergebnis falsch ist.

Gerade bei CNF könnte es aber sein, dass in der Aufgabenstellung steht: "Geben Sie alle Zwischenschritte an." Und dann ist es natürlich verlangt, alle hinzuschreiben. (Wenn sich in einem Schritt keine Veränderung ergibt, dann logischerweise nicht!)

Beantwortet: kann ich Schritt "(1) G lambda-frei machen" nicht IMMER ohne neuen Startzustand S' machen?

Wed, 22 Oct 2014 15:05:07 +0000

Hallo,

diese beiden Produktionsmengen sind nicht äquivalent:

{ S --> SS | [S] | lambda }

bzw.

{ S --> SS | [S] | S | [ ] }

Mit der unteren Menge kann das leere Wort nicht erzeugt werden, oben schon. Damit man auch unten das leere erzeugen kann, könnte man bspw. ein neues Startsymbol S' einführen, zusammen mit der Regel S' --> S | lambda. Auf diese Weise erhält man nach Anwendung des ganzen Algorithmus eine Grammatik, die in CNF ist und trotzdem das leere Wort erzeugen kann (im CYK-Algorithmus muss man die lambda-Regel dann separat betrachten.

Viele Grüße

Lukas König

Nachtrag:

Sie haben allerdings Recht damit, dass bei der Nachklausur 2013 die Regel S --> AB fehlt. Ich habe das korrigiert.

Viele Grüße

Lukas König

Beantwortet: Dieser Aufgabentyp in der Klausur zu erwarten?

Wed, 22 Oct 2014 15:03:19 +0000

Die CYK-Aufgaben in den Klausuren sind viel moderater als diese Aufgabe. Wir wollen ja nur sehen, ob Sie das Prinzip verstanden haben, und nicht testen, ob Sie sich sich für eine halbe Stunde in das Innere eines Computers versetzen und einen stumpfsinnigen Algorithmus durchführen können :-)

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen

Beantwortet: warum ist bei Teil b), m=4 an der Stelle des ersten Cs nur C eingetragen?

Wed, 22 Oct 2014 15:01:06 +0000

Hallo,

du hast Recht, nach den Regeln sollte das eigentlich da stehn. Aber diese Regelung ist eben eine Ausnahmeregelung auch für die Grammatik, deshalb muss man da etwas anders betrachten. Unten in der Grammatik steht auch, dass wir mit S auch immer S' in das Kästchen schreiben müssen. Also identifizieren wir S' mit S und gucken deshalb auch nicht auf die Regel S'->S sondern quasi für S als auch S' für die Produktion, die S erzeugt.

Also anders gesagt, die übergänge von S' werden ignoriert und S' schreiben wir immer du S in das kästchen dazu.

Gruß,

Adam (Tutor)

Beantwortet: Verfahren zu Teil c)?

Wed, 22 Oct 2014 15:00:02 +0000

Hallo,

ein wirkliches Verfahren gibt es da nicht. Manche Grammatiken machen es einfach, z.B. die rechtslinieare Grammatik. Aber das wirst du wohl oder übel mit "scharfem Hinsehen" lösen müssen.

Gruß,

Adam (Tutor)

Beantwortet: Lösungsweg korrekt?

Wed, 22 Oct 2014 14:58:55 +0000

Hallo,

ja, das passt so.

Viele Grüße

Philippe (Tutor)

Beantwortet: Wenn ein Zustand ein leeres Wort erzeugt kann ich Lamda weglassen?

Wed, 22 Oct 2014 14:57:50 +0000

Hallo,

schaue dir für diese Frage am besten mal die Lösung der Aufgabe 78 an.

Wie du siehst, kannst du das Lambda nicht einfach weg lassen. Du musst in allen Übergangsfunktionen gewährleisten, dass das jeweilige Nonterminalsymbol (in diesem Beispiel das B) einfach wegfallen kann. Dazu fügst du quasi die gleiche rechte Seite jeweils nochmal hinzu, nur dass dabei dann das entsprechende Symbol (hier B) weggelassen wird.

Viele Grüße

Lukas

Beantwortet: Produktion des Wortes?

Wed, 22 Oct 2014 14:55:24 +0000

Die Idee ist, sich anzuschauen, aus welchen CNF-Regeln eine Kette x von Terminalen entstanden sein kann. Für eine Teil-Kette x0 der Länge 1 (ganz zu Beginn des Algorithmus) schaut man sich die Regeln an, die auf der rechten Seite genau x0 stehen haben und merkt sich deren linke Seiten, aus denen x0 entstanden sein könnte. Danach schaut man sich an, aus welchen Symbolen diese linken Seiten entstanden sein könnten, wobei man dafür immer zwei Symbole auf einmal betrachten muss, da so der Aufbau der CNF-Regeln ist. So arbeitet man sich zu immer längeren Teilfolgen der Kette, bis man irgendwann weiß, aus welchen Symbolen die gesamte Kette abgeleitet werden kann. Wenn S dabei ist, weiß man, dass man x mit der Grammatik ableiten kann.

Genauer will ich das hier nicht beschreiben, da es ja auf den Vorlesungsfolien genau beschrieben ist. Außerdem ist diese Animation hilfreich für das Verständnis. Falls Sie aber noch konkrete Fragen haben, beantworten wir die natürlich gerne.

Viele Grüße

Lukas König

Beantwortet: warum ergibt eigentlich die leere Menge und S/S' nicht wieder S?

Wed, 22 Oct 2014 14:54:26 +0000

Die leere Menge mit irgendetwas kombiniert ergibt immer die leere Menge, denn Sie brauchen in CNF ja immer zwei Symbole von einem Ableitungsschritt zum nächsten, also eines aus der einen Menge und eines aus der anderen.

Viele Grüße

Lukas König

Beantwortet: S durch Produktionen ersetzen?

Wed, 22 Oct 2014 14:53:14 +0000

Hallo,

der Teil S'->S ist nicht in Chomsky-Normalform, wird aber benötigt, um zu gewährleisten, dass auch das leere Wort zur Sprache gehört.
Bezüglich des Cocke-Younger-Kasami-Algorithmus gilt, dass Sie diesen auch nur auf den Teil in Chomsky-Normalform (also ohne S'->S) anwenden. Demnach muss also im letzten Feld S auftauchen. Sie können aber S' auch, wie in der Musterlösung, mitschleppen.

Viele Grüße

Friederike Pfeiffer

Beantwortet: Fehler in der Tabelle?

Wed, 22 Oct 2014 14:51:26 +0000

Hallo,

der Zelleninhalt ist eigentlich richtig. Die Terminalsymbolkombinationen, die Sie überprüfen müssen für m=3 und zweites c, sind CA, CG und CC. Da diese aber nicht in der Grammatik vorkommen, ist der entsprechende Zelleninhalt leer.

Freundliche Grüße
Friederike Pfeiffer

Beantwortet: Wieso ist Übergang S->Lambda nötig?

Wed, 22 Oct 2014 14:47:49 +0000

Hallo,

in diesem Fall wäre das auch in Ordnung. Unsere Vorgehensweise ist aber in dem Fall notwendig, wenn der Startzustand auch auf mind. einer rechten Seite vorkommt - wir müssen dann nämlich gewährleisten, dass zwar das leere Wort erzeugt, aber nicht in einem späteren Schritt abgeleitet werden kann.

Viele Grüße

Lukas König