Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in END-AA

Beantwortet: Frage zur Aufgabe 3

Mon, 14 Feb 2022 07:52:51 +0000

Im Zustand s1 gab es aus dem vorherigen Schritt einen Übertrag in s0 nicht.
D.h. bei s1 mit 01 ist es 0-(1+1)=1-1-1=0(1) (4. Zeile der Tabelle, in Klammern steht der Übertrag), es wird also 0 ausgegeben und ein Übertrag, man bleibt also in s1.
Bei der Eingabe 10 kommt (wieder mit dem Übertrag davor) 1-0-1 = 0 (0), also wird 0 ausgegeben und man wechselt in Zustand s0, da es keinen Übertrag mehr gibt

Beantwortet: verstandnis

Sat, 22 Jan 2022 14:54:17 +0000

Ja genau, a, b und c stehen für je ein Bit und es ist a-b (-c) = d (c'). c ist der Übertrag aus dem Schritt davor.

101 a
-010 b
(100) c bzw. c'
011 d

hier wird es dreimal genutzt die a,b,c, erst mit dem jeweils rechtesten Zeichen, dann mit dem mittleren und zum Schluss mit dem ersten Zeichen.

Falls noch etwas unklar ist, frage gerne noch einmal nach.

Viele Grüße
Anne (Tutorin)

Beantwortet: GdInfoII 2-6 - Beispiel Zustandstafel

Fri, 20 Nov 2020 11:06:36 +0000

Hallo,

zunächst einmal hast du natürlich recht, dass das Garagentor Beispiel eine Vereinfachung darstellt. Sicherlich wäre es sinnvoll, Fehler abzufangen und entsprechende Szenarien abzubilden, allerdings erhielte man dann einen EA mit weitaus mehr Zuständen, was in diesem einfachen Beispiel alles andere als zielführend wäre. In der Vorlesung ging es primär darum, einen Praxisbezug herzustellen.

Generell ist es also in der Praxis durchaus üblich, solche Vorgänge mit State Machines zu simulieren, allerdings eben in einer vereinfachten Form.

LG, Martin

Beantwortet: Endlicher Automat

Sun, 09 Feb 2020 08:10:07 +0000

1) Nein

Du kannst Lambda nicht auf einen Pfeil schreiben... d(s, lambda)-->s ist immer automatisch bei jedem Zustand mit dabei, da du hierbei ja einfach in dem Zustand bleibst.

2) Es muss von jedem Zustand aus genau definiert sein, wo man mit welcher Eingabe hinkommt... und das für alle möglichen Eingabezeichen. ...gehört a zum Eingabealphabet, so muss bei jedem Zustand klar sein wo man hin kommt falls ein a eingegeben wird.

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

Beantwortet: Angabe Produktionsfunktion bei nEA -> EA

Wed, 08 Jan 2020 08:55:46 +0000

Hallo uqysn,

wenn der EA vollständig angegeben werden soll, dann sollen Sie auch den dazugehörigen Graphen angeben.

Viele Grüße

Alex (Tutor)

Beantwortet: Meine Frage bezieht sich auf die zweite Tabelle in der Lösung

Wed, 23 Jan 2019 17:25:09 +0000

Diese Tabelle macht für mich keinen Sinn auch wenn ich Zeilen vertausche.

Beantwortet: Bonusklausur 2018, Aufgabe 1 Wie kommt man auf die Zustandsüberführungstabelle in der Lösung?

Mon, 21 Jan 2019 17:30:41 +0000

Hallo uvtpu,

1.Bei der Zustandsüberführungstabelle fängst du beim Startzustand an und betrachtest die Folgezustandsmengen bei Eingabe a/b.
2. Als nächstes betrachtet man die Folgezustände dieser Zustandsmengen.
3. Schritt 2 wird solang wiederholt, bis man für alle Mengen die Folgezustände berrechnet hat.

Die Tabelle stellt dar von welchem Zustand aus Kanten in welche Zustände gehen (von z.B. für a und s0 in s1,2,3).

Wenn die Tabelle gegeben ist (Aufgabe ist aber auch ohne Tabelle Lösbar), kann man sehr einfach die Folgezustandsmengen aus ihr ablesen in dem man die gegebenen Mengen miteinander vereint:

z.B.: Folgezustandsmengen für die Zweite Zeile der Lösung:
{s0,s2} \ a = {s0}\a vereinigt mit {s2}\a ={s0,s2,s3} + {} = {s0,s2,s3}

Viele Grüße
Philipp (Tutor

Beantwortet: regulärer Ausdruck Folie 2-62

Sun, 12 Nov 2017 11:30:53 +0000

Hallo,
ich glaube du hast bei der Sprachdefinition einen kleinen Denkfehler. Der Reguläre Ausdruck beschreibt eine Sprache" zu welcher Wörter gehören die entweder aus beliebig vielen a bestehen ODER aus einem ab. Wörter wie aaab gehören nicht dazu. Mit diesem Wissen solltest du dir deine Frage jetzt selbst beantworten können, wenn nicht frag einfach nochmal.

Leibe Grüße
Verena (Tutor)

Beantwortet: Wann ist Binärzahl mod m = 0 - Darstellung EA

Sun, 12 Feb 2017 13:53:11 +0000

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!

Beantwortet: Aufgabe 41 b aus dem Aufgabenpool - EAs

Tue, 10 Jan 2017 14:46:32 +0000

Hallo,
da hier nach einem deterministischen endlichen Automaten gefragt wurde, muss für jede Eingabe in jedem Zustand ein Übergang existieren. Würden wir den Zustand S3 entfernen, und damit auch alle Übergänge die in diesen Zustand führen dann währe der Automat nicht mehr deterministisch.

Grüße, Sören (Tutor)

Beantwortet: Aufgabe 1 Aufgabenpool

Sun, 13 Nov 2016 15:53:27 +0000

Der Unterschied zwischen einem Mealy- und einem Moore-Automaten liegt in der Definition der Ausgabefunktion. Bei Mealy-Automaten hängt die Ausgabe von Eingabesymbol und Zustand ab, d.h. die Ausgabefunktion hat die Form
$\gamma: S \times E \rightarrow A $ Daher wird die Ausgabe im Zustandsdiagramm bei den Kanten/Zustandsübergängen angegeben. Bei Moore-Automaten hängt die Ausgabe nur von dem Zustand ab, d.h. die Ausgabefunktion hat folgende Form
$\gamma: S \rightarrow A$ Da die Ausgabe unabhängig von der Eingabe ist, wird sie im Zustandsdiagramm zu den Zuständen/Knoten geschrieben (also in die von dir genannten „Blasen“).

Bei der Umwandlung eines Moore- in einen Mealy-Automaten wird also die Ausgabefunktion angepasst. Die zu einem Zustand $s$ gehörende Ausgabe bei Moore-Automaten entspricht bei Mealy-Automaten der Ausgabe bei allen Zustandsübergangen, die in Zustand $s$ landen.

Ich hoffe, das war hilfreich. Wenn es noch nicht klar ist, einfach nochmal fragen.

Viele Grüße Philipp (Tutor)

Beantwortet: Aufgabe 7 a) Ich verstehe nicht, was zum Einen ein Binärstring ist und wieso der EA so aussieht?

Sun, 24 Jan 2016 23:09:59 +0000

Binärstring = String der nur aus 0en und 1en besteht (binär)

Der Automat akzeptiert jedes Wort, das nicht auf 1 endet, denn dann wäre die resultierende Dualzahl ungerade. Du musst also alle binäre Eingaben als Dualzahl interpretieren. Wenn du z.B. 11 als Dualzahl interpretierst erhältst du den Wert 3 ( 3 mod 2 = 1) und damit kein Wort der Sprache L. Dein Fehler liegt vermutlich darin, dass du 1+1 gerechnet hast und die Zahl nicht als Binärzahl betrachtet hast.

Beantwortet: Umbenennung der Zustände

Thu, 07 Jan 2016 12:17:25 +0000

Hallo,

Sie dürfen die Zustände benennen, wie Sie wollen. Achten Sie nur darauf, dass Sie nicht dieselben Namen benutzen wie im Ursprungsautomaten (wobei wir auch das nicht so eng sehen). Hauptsache, der Automat stimmt strukturell und die Definition ist vollständig und eindeutig.

Eine Konvention gibt es in der Vorlesung trotzdem, wir nennen die Zustände meistens $s_0, s_1, \ldots$ bzw. $s'_0, s'_1, \ldots$ usw., wobei das $s$ für "state" steht. Das ist sinnvoll, um die Lesbarkeit zu erhöhen - und wenn Sie sich das auch so angewöhnen, hier und bei den anderen Themen, kann das sicher nicht schaden - aber wir ziehen Ihnen sicher in der Klausur keine Punkte ab, wenn Sie sich nicht daran halten.

Viele Grüße

Lukas König

Beantwortet: Wahrheitstabelle für bitserielle Subtraktion

Tue, 14 Oct 2014 14:23:11 +0000

Hallo,

zunächst muss man sich überlegen, was bei der Subtraktion wichtig ist. Zunächst überlegen wir uns, dass wir bei der Subtraktion eine Stelle nach der anderen betrachten, wie beim schriftlichen Subtrahieren.

Wir benötigen zwei Zahlen, die eine wird von der anderen abgezogen. Dann kann es noch einen Übertrag geben, der von der vorherigen Rechnung kommen kann (Wir betrachten eine Differenz einer binären Zahl mit beliebiger Länge).

Wir erhalten das Ergebnis der Rechnung und einen eventuellen Übertrag. Wenden wir das auf die Aufgabe an:

a ist die aktuelle Zahl, die wir betrachten, die Zahl b ziehen wir von ihr ab. c ist der Übertrag der vorherigen Rechnung.

Unser Ergebnis ist das d und unser neuer Übertrag c' (sieht übrigens genauso aus wie der Volladdierer, siehe das Kapitel über Schaltnetze).

Das soll einem ein bisschen bei der Zeichnung helfen nehme ich an.

Der Zustand sagt mir, ob ich im Moment einen Übertrag aus der vorherigen Rechnung habe (s1) oder eben nicht (s0). Die ersten beiden Zahlen beschreiben die Rechnung, dabei liest man "Erste Zahl - Zweite Zahl", nach dem Komma steht dann das Ergebnis mit Berücksichtigung des Übertrages (also muss ich auf den Zustand gucken, in dem ich mich befinde). Der neue Übertrag wird dadurch realisiert, dass ich in den richtigen Zustand wechsel.

Gruß,

Adam (Tutor)

Beantwortet: Lesen des Mealy Automaten

Tue, 14 Oct 2014 14:19:32 +0000

beim Übergang steht ja immer $ab,c$

dabei gilt $a - b = c$

der Zustand s0 bedeutet, dass es danach keinen Übertrag gibt; der Zustand s1 steht jedoch für den Übertrag.

deswegen gilt ohne Übertrag:

0-0=0 kein Übertrag

1-0=1 kein Übertrag

1-1=0 kein Übertrag

0-1=1 wechsle in Übertrag

bei Übertrag gilt dann:

0-0=1 Übertrag

1-1=1 Übertrag

0-1=0 Übertrag

1-0=0 wechsle in kein Übertrag

hoffentlich ist das jetzt klarer...