FMI01 am 12.08.11

[halminator]

Hallo,

hier die notwenigen Infos:

Aufgabe 1:
Geben Sie
(a) das Zustandsdiagramm und
(b) die Automatentafel
eines Mealy-Automaten A an, dessen Ein- und Ausgabealphabet die Menge f0; 1g ist. Jedes
Ein- und Ausgabewort wird als im Dualsystem dargestellte naturliche Zahl interpretiert. Der
Automat soll die eingegebene Dualzahl inkrementieren, d.h. eine 1 hinzuaddieren und diese
ausgeben.
Beispiel: Eingabe 0011 (dezimal 3), Ausgabe: 0100(dezimal 4).


Aufgabe 2: (so ähnlich)
Geben Sie
(a) das Zustandsdiagramm und
(b) die Automatentafel
eines deterministischen endlichen Automaten an, der genau die Wöorter akzeptiert, die das
Teilwort abc oder acb enthalten.

Aufgabe 3: (so ähnlich)
Aufgabe Gegeben ist die Automatentafel des folgenden Automaten:
a b
s0 s1 s0
s1 s3 s2
s2 s2 s1
s3 s4 s3
s4 s0 s5
s5 s5 s4
Der Zustand s0 ist der Anfangszustand und der Zustand s4 ist der einzige Endzustand von
diesem Automaten.
(a) Geben Sie das Zustandsdiagramm an.
(b) Minimieren Sie den Automaten, falls der Automat nicht minimal ist.

Aufgabe 4:

Aufgabe 2.4 Korrekte Klammerwörter mit den beiden Klammertypen runde Klammern (,)
und eckige Klammern [,] sind wie folgt deniert:
1. Die Wörter ( ) und [ ] sind korrekte Klammerwörter.
2. Ist w ein korrektes Klammerwort, dann auch ww, (w) und [w].
3. Nur Wörter, die nach den Regeln 1. und 2. gebildet werden können, sind korrekte Klammerw
örter.
Geben Sie die Funktionstafel der partiellen Überführungsfunktion für einen deterministischen
Kellerautomaten an, der genau die korrekten Klammerwörter akzeptiert.
Formal: Gesucht ist der dpda A mit der Eigenschaft: L(A)=fw j w ist ein korrektes Klammerwortg.

Komplex:

Suchbäaume stellen eine Datenstruktur

(a) Geben Sie für den folgenden Binärbaum an, ob es sich um einen Suchbaum handelt. Begr
ünden Sie Ihre Antwort.

(b) Geben Sie die Folge der Knotenwerte an, wenn die Knoten des Baumes in der
1. Hauptreihenfolge (preorder) 2. Nebenreihenfolge (postorder) und 3. Symmetrischen Reihenfolge
(inorder) durchlaufen werden.
(c) Geben Sie für die Werte 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30 einen Suchbaum an, der
diese Werte als Knotenwerte enthalt und in dem alle küzesten Pfade von der Wurzel bis
zu einem Blatt dieselbe Länge haben. Es genugt, eine grasche Darstellung dieses Baumes
anzugeben, ein Hinweis darauf, wie man algorithmisch vorzugehen hat, ist nicht verlangt.

Teilaufgabe
(a) Beschreiben Sie einen Algorithmus (als Struktogramm, als Pseudo-Code oder als Code in
einer Ihnen bekannten Programmiersprache) fur eine Funktion (oder Prozedur), die in einem
Suchbaum nach einem Wert sucht. Falls der Wert im Baum enthalten ist, soll eine Eins zuruckgegeben
werden, andernfalls eine Null.

Geben Sie
(a) das Zustandsdiagramm oder (b) die Automatentafel eines Mealy-Automaten A an, dessen
Ein- und Ausgabealphabet = f0; 1g ist. Jedes Eingabewort soll von dem Automaten
in das sogenannte Zweier-Komplement umgewandelt werden. Das Zweier-Komplement ist die
heute ubliche Darstellung negativer Zahlen im Rechner. So wird z.B. die Zahl -5 in einem 8-
bit Maschinenwort durch die Bitfolge 1111 1011 dargestellt. Eine bitweise Addition zu dieser
Bitfolge zur Darstellung der Zahl 5 (0000 0101) ergibt die Bitfolge 0000 0000, die Darstellung
der Null als 8-bit Maschinenwort.
Das Zweier-Komplement einer Zahl n 2 N erhalt man dadurch, dass die Dualdarstellung
der Zahl n bitweise komplementiert wird und zu dem Komplement eine 1 hinzu addiert wird:
5 ) 00000101 ) 11111010 ) 11111011 ) 5

Konstruieren Sie einen Mealy-Automat, der jede Folge aus Nullen und Einsen in das Zweier-
Komplement uberfuhrt.
Weiteres Beispiel: Eingabe 0011, Ausgabe: 1101.

Komplex 3: Kellerautomat Grammatik usw

[Rumtata106]

Wow - das ist mal eine Zusammenfassug - Hut ab!

Bei der zweiten Detail, glaube ich mich zu erinnern, dass hier ein DEA gefragt war, der uax nicht akzeptierte, wobei E={a,b,c}, x=ein Symbol aus E und u=ein Symbol aus E oder Lambda sein sollte.

Die dritte Komplex war die Aufgabe aus dem PDF S.18 in leichter Abwandlung.

Ich fand, dass Herr Valkema für meine Belange ein Super-Seminar (23.07) hingelegt hat. Man merkte förmlich, dass er Spaß an dem Thema und an der Vermittlung daran hatte. Und das ganze ohne Beamer & PowerPoint-War - echt klasse!

[monday55]

gute Zusammenfassung, hut ab.
-> ich hätte nur eine Korrektur.
Man sollte entweder den Graph oder das Zustandsdiagramm angeben.

[halminator]

Noten sind online...puhhh nun ist es geschafft...

[monday55]

joar knappe Kiste, ick sag nur 4 Gewinnt