FMI20 vom07.04.2018

Algorithmus, Baumdurchlauf, Compiler, Interpreter...; Cobol, Pascal, C/C++, Java & Co.
Antworten
TobiHo
Forums-Profi
Forums-Profi
Beiträge: 47
Registriert: 29.08.13 12:54

Detailaufgaben

A1
NEA mit Automatentafel und Zustandsgraph zur Sprache 0^n 1^(n+1)

A2
Grammatik bauen

A3
Kellerautomaten inkl Zustandsgraph und Automatentafel

A4
O Notationen inkl ordnen

Komplex

B 1.1
NEA bauen
B 1.2
NEA in DEA umwandeln
B 1.3
DEA kürzen

B.2.1
PDA bauen

B 2.2
Grammatik zur selben Sprache

B 2.3


B2.4
Irgendwas mit Regulären Audrücken und Gleichungen aufstellen, konnte ich nicht
FMI101, Kapitel 6.3

B3.x War Turing und Komplexitätstheorie, hab ich nicht mal richtig gelesen


Wenn noch jemand geschrieben hat & mehr weiß, will ich das gerne ergänzen
Morphus
Mitglied
Mitglied
Beiträge: 27
Registriert: 17.08.12 14:56

Ergänzungen von mir soweit ich es noch weiß:

Detail:
A1. NEA erzeugen der auf "12" oder "122" endet. Automatentafel und Zustandsdiagramm angeben
A2. Typ3-Grammatik erzeugen, der den NEA aus A1 erzeugt. Grammatik formal angeben und zwei Wörter mit der Grammatik ableiten und die Ableitungsregeln angeben
A3. Kellerautomaten erzeugen, der die Sprache 0^k 1^k+1 erkennt. Diesen auch formal angeben plus Zustandsdiagramm und Automatentafel
A4. 4 oder 5 O-Notationen erzeugen / umformen und der Größe nach sortieren.

Komplex B1: NEAs, DEAs, Umformung, Minimierung
B1.1/2 Aus einer gegebenen Automatentafel einen NEA zeichnen, den NEA in DEA umwandeln, DEA anschließend minimieren und die Automatentafel und das Zustandsdiagramm am Schluss angeben.
B1.3 Zu einem gegebenen DEA sollte man:
a) Gleichung aufstellen
b) Gleichung lösen
c) Regulären Ausdruck angeben (siehe Kapitel 6.5 aus FMI101)

Komplex B2: Kellerautomaten
Kellerautomaten mit der Sprache L={ 0^m+n 1^m 2^n | m > 0; n >= 0}
B2.1 Grammatik erstellen, der den Automaten erzeugt. Wort aus der Grammatik ableiten und Ableitungsregeln angeben. Grammatik anschließend in die Chomsky Normalform überführen
B2.2 PDA erstellen (Automatentafel + Zustandsdiagramm). Entweder den PDA aus der Grammatik von B2.1 erzeugen, oder den PDA aus der Sprache direkt bauen. Anschließend Konfigurationsfolge zu einem Wort angeben.

Komplex B3: Turing Maschinen und Komplexität
Hab das nur ganz kurz überflogen. Was ich gelesen hatte war:
B3.1 Man sollte eine Turing Maschine bauen, die alle Werte auf einem Band durch 1 ersetzt
B3.2 irgendwas zu k-CLIQUE wurde geprüft, also sowas wie erklären und Aufgabe dazu
Antworten