Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-4-2

Beantwortet: Ist ein lambda-Übergang bei CNF erlaubt?

Tue, 14 Jan 2020 10:55:24 +0000

Hallo,

ein Lambdaübergang ist aus dem Startzustand S heraus erlaubt, sofern S auf keiner rechten Seite vorkommt. Dies dient dazu, auch das leere Wort mit der Grammatik in CNF erzeugen zu können.

Viele Grüße

Moritz (Tutor)

Beantwortet: Tutorium 4 Folie 18 + 19 FEHLER?

Thu, 02 Jan 2020 22:42:27 +0000

Die Folien vom Tutorium 4 wurden entsprechend angepasst und hochgeladen.
Viele Grüße,

Sören (Tutor)

Beantwortet: DNF aus BDD ablesen A3b)

Fri, 04 Jan 2019 10:58:57 +0000

Hallo uvlpj,

um die DNF aus dem BDD zu lesen musst du lediglich alle „Wege zur 1“ aufschreiben (diese beginnen immer mit der ersten Variablen, in diese, Fall x). Z.B. xˋyˋzˋ ist eine mögliche/gültige Belegung, also „nicht x“ und „nicht y“ und „nicht z“ führt zur 1. Die einzelnen Wege musst du danach mit + verbinden, da alle Wege, die zur 1 führen erlaubt sind und es dabei egal ist, ob du Weg 1 oder Weg 2 gehst.

ist es nun klarer?

viele Grüße

Anne (Tutor)

Beantwortet: Ist KNF/DNF direkt aus BDD ablesbar?

Mon, 21 Sep 2015 07:14:11 +0000

Hallo,

Deine Boolsche Funktion beschreibt ja prinzipiell die Zustände in DNF, bedeutet, das musst du nur umschreiben, wenn du x,y,z als Aussagen betrachten wolltest. Die KNF musst du anschließend durch Umformung bilden, allerdings werden in der Regel nach BDDs die Boolschen Funktionen abgefragt und nicht die KNF und DNF, da sie hier doch ein wenig fehl am Platz wären.

Ich hoffe ich konnte helfen ;)

Viele Grüße

Marc (Tutor)

Beantwortet: b): Wie muss man hier ansetzten?

Mon, 21 Sep 2015 07:12:43 +0000

Hallo!

In der b) ist nach der Boolschen Funktion gefragt, die praktisch angibt, wann dein BDD den Wert 1 ergibt. Du betrachtest also einfach alle Wege über x, y, z, die am Ende zum Blatt "1" führen und verknüpfst diese mit "+" in der Boolschen Funktion, was dem "oder" entspricht.

In der Musterlösung wurden die drei Wege am Ende noch geschickt zusammengefasst: Direkt ablesen lassen sich die Wege x'y'z' und xz und x'yz . Beim zweiten Weg (xz) taucht das y ja nicht mehr auf (dieser Knoten wurde beim Erstellen des BDD eliminiert), was bedeutet, dass der Wert von y (0 oder 1) auf diesem Weg egal ist für den Endwert der Boolschen Funktion. Dh das man xz aufspalten kann in xyz und xy'z. Vergleicht man nun xyz mit dem abgelesenen dritten Weg x'yz, so sieht man, dass es egal ist, ob x oder x' vor der Kombination yz steht, beidesmal nimmt die Boolsche Funktion den Wert 1 an. Dh. der Wert von x ist irrelevant und kann deshalb bei diesem Weg weggelassen werden.

Daher ergeben sich am Ende in zusammengefasster Version die 3 Wege: x'y'z' , xz und yz , die in der Boolschen Funktion mit "+" verknüpft werden.

Ich hoffe, ich konnte dir weiterhelfen!

Grüße,

Janine (Tutorin)

Beantwortet: Erklärung zu Punkten 1. - 3. ?

Mon, 21 Sep 2015 07:09:31 +0000

Hallo,

du versuchst in diesem Baum gleiche Pfade zusammenzufassen. Dabei beginnst du bei den Blättern des Baums.

Im ersten Schritt werden die 8 Blätter zusammengefasst und zwar so, dass ich nur noch eine null und eine eins vorkommt.

Im zweiten Schritt erkennt man, dass bei den beiden grauen z's genau das gleiche passiert. Immer wenn eine eins vorkommt komme ich zu zu eins, wenn eine 0 vorkommt komme ich am zur 0.

Im dritten Schritt ist bei den beiden z's wieder der gleiche Fall. Bei einer null komme ich zu einer 0, und bei einer eins zu einer 1. Also kann ich diese wieder zusammenfassen.

Viele Grüße,

Sebastian (Tutor)

Beantwortet: a): Warum kann Y im 2. Schritt weggelassen werden?

Mon, 21 Sep 2015 07:08:20 +0000

Guck dir den Lösungsweg an, hier wird es klar:

Im vorletzten Schritt hast du an der abgehenden Kante von dem rechten y ein 0/1, also ist es egal, ob du für y 0 oder 1 einsetzt. Da du hierher mit x=1 kommst bleibt diese 1 erhalten.

Gruß

Philip (Tutor)

Beantwortet: b): Warum wird x' weggelassen?

Mon, 21 Sep 2015 07:05:26 +0000

Hallo,

wenn du das schreiben würdest, wäre das für die Klausur vollkommen ok. In der Musterlösung wird hier gekürzt. Du hast wahrscheinlich

x'y'z' und xz und x'yz,

du kannst die beiden letzteren miteinander kürzen.

Grüße,

Jördis ( Tutorin )