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 von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
1.8k Aufrufe
Hallo,

 

Ist gefragt, wann n mod 2 = 0, so ist klar wie hier der Automat erstellt werden muss. Ist jedoch n mod 7 = 0 oder ähnliches gefragt, so ist mir dies noch nicht ganz klar. Ich weiß, dass eine Binärzahl durch 3 teilbar ist, wenn ihre alternierende Quersumme durch 3 teilbar ist. Wie realisiere ich das am besten in einem EA? W

Danke im Voraus
in END-AA von upcws upcws Tutor(in) (101k Punkte)  
0 0
Hallo, auf welche Aufgabe bezieht sich deine Frage?
Du hast in der Kategorie END-AA geschrieben und da geht es um einen Mealy Automaten zur bitseriellen Subtraktion.

Viele Grüße

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
Beste Antwort

Für allgemeine $m$ und $n$ in Dualdarstellung ist das durch endliche Automaten gar nicht lösbar. Dafür müsste man ja die eine Zahl durch die andere teilen, wofür man mehr Rechenleistung benötigt als endliche Automaten bieten.

Für einige spezielle $m$ wie $2$ oder $3$ ist es natürlich lösbar, da würde wir aber im Zweifel in der Klausur angeben, wie Sie vorgehen müssen. Das mit der alternierenden Quersumme können Sie ja mal versuchen.

Auch wenn $n$ in Unärdarstellung vorliegt, wenn es also nur um die Länge der Eingabe geht, kann für jedes feste $m$ ein endlicher Automat angegeben werden, der genau dann akzeptiert, wenn die Länge der Eingabe $n=|w|$ durch $m$ teilbar ist. Versuchen Sie sich mal zu überlegen, wie das geht, das ist eine gute Übung!

von Dozent (10.1m Punkte)  
ausgewählt von upcws upcws
0 Pluspunkte 0 Minuspunkte
Hallo upcws!

Das ist schon eine sehr spezielle Frage. Wenn es irgendwo eine ähnliche Aufgabe gibt könnte ich dir vielleicht besser helfen, aber zwischen durch 2 teilbar und durch 3 teilbar liegen ja noch einige Schwierigkeitsstufen.

Ich habe mich damit auseinander gesetzt und keine direkte Lösung gefunden. Hier kannst du dich da drüber informieren, falls es dich sehr interessiert:

http://www.math.uni-bremen.de/didaktik/ma/ralbers/Publikationen/Dissertation/K7_EndlAutomat.pdf

Grüße, Felix (Tutor)
von uwdtl uwdtl Tutor(in) (103k Punkte)  
...