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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

0 Pluspunkte 1 Minuspunkt
260 Aufrufe
Guten Tag,

Ich habe die Vorgehensweise der 3. Aufgabe der Bonus Klausur 2017 gefolgt um diese Aufgabe zu lösen und bin zu diesen Ergebnissen angekommen:

(ich habe hier ' als Negation benutzt, sorry ich konnte die Funktionen nicht anderes schreiben)

a=q0 oder q1'

q0= (e' und q*0 und q*1') oder (e und q*0' und q*1)  oder (e und q*0 und q*1')

  = (q*0und q*1') oder (e und q*0' und q*1)

q1= e und q*0' und q*1'

Normalerweise skizziere ich jetzt das Schaltwerk und fertig. Ich kann aber die Skizze in der Lösung gar nicht nachvollziehen.

Habe ich einen Fehler hier gemacht ? Wie kommt man auf dieses Schaltwerk der Lösung?

Vielen Dank im voraus
in SCH-AE von uodys uodys Lernwillige(r) (870 Punkte)  
0 0
a=q0 UND q1'

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte

Hallo,

Wie in der Lösung steht, kommt man nicht algorithmisch auf das angegebene Schaltwerk, sondern durch "scharfes Hinsehen".

Dabei ist das ODER-Gatter die entscheidene Komponente, die dafür sorgt, dass das Schaltwerk nachdem es zwei Einsen hintereinander gelesen hat, für immer Eins ausgibt.


Die unten angegebene alternative Lösung über die Wahrheitstabelle ist wie folgt zu verstehen:
 

  • E ist der Kanal über den die Eingaben laufen
    (jeweils eins der Reihe nach.)
  • t ist der Taktgeber (für die Aufgabe nicht weiter wichtig)
  • Das obere Flipflop entspricht dem ersten Index in den Automatenzuständen, das untere Flipflop entspricht dem zweiten Index.
    (Beispiel zur Verdeutlichung: Automatenzustand S_01 -> oberes Flipflop=0, unteres Flipflop=1)
  • Der Wert des oberen Flipflops ist auch gleichzeitig der Wert unserer Funktion. Auch das können Sie sich gut am unten angegebenen Automaten verdeutlichen.
  • Die nicht ausgefüllten Felder in der Wahrheitstabelle sind mit unserer Konfiguration für f1* und f2* nicht zu erreichen.

Sie sehen also die unten angegebene Wahrheitstabelle hängt immer nur von einem Eingabesymbol und ansonsten dem Wert der Flipflops ab.

So ist auch die gegebene Boolsche Funktion in DNF direkt aus der Wahrheitstabelle abgeleitet

Aus dieser DNF können Sie selbstverständlich ein Schaltwerk konstruieren, indem Sie die Boolschen Ausdrücke für f1* f2* genau abbilden. 

[EDIT]
Ihr Lösung stimmt ja bis auf a= ... mit der Musterlösung überein.
a=q0 oder ~q1 ist jedoch nicht richtig, da das Schaltwerk so auch z.B. die Eingabe 00 akzeptiert, was natürlich nicht in der verlangten Sprache liegt.

Gruß
Laurin (Tutor)

von ujegu ujegu Tutor(in) (103k Punkte)  
Bearbeitet von ujegu ujegu
0 0
Guten Abdend,
es ist mir schon klar wie man den Automat, Wahrheitstabelle und DNFs aufstellt. Meine Frage ist: Diese Funktionen entsprechen nicht der Skizze in der Lösung. Wäre eine Darstellung dieser Funktionen als Schaltwek eine alternative Lösung ?
e ist äquivalent zu E, q0=f1* und q1=f2* sind aktuelle Ausgaben der Flipflops(jeweils obere und untere) und q*0=f1, q*1=f2
0 0
Hallo,
ich habe die Antwort oben präzisiert.
Hilft Ihnen das weiter?
0 0
q0 UND q1', Ich habe es falsch getippt und in meinem ersten Kommentar korrigiert.
Wäre dann die Darstellung der Funktionen als Schaltwerk eine richtige Lösung für die Aufgabe ?
0 0
Ja, das wäre eine richtige Löusng.
...