FMI11 am 19.11.2016 in Karlsruhe

Algorithmus, Baumdurchlauf, Compiler, Interpreter...; Cobol, Pascal, C/C++, Java & Co.
Antworten
spitfire78
Mitglied
Mitglied
Beiträge: 15
Registriert: 12.04.09 11:46

Hallo zusammen,

hier die Prüfung vom 19.11.2016 soweit ich mich noch erinnern kann. Gerne ergänzen.

Detailaufgaben
- NEA konstruieren (Graph und Automatentafel), der Worte akzeptiert, die auf 12 oder 122 enden. Dazu Grammatik angeben und 2 Worte ableiten. Dann noch einen regulären Ausdruck angeben, der diesen NEA definiert.
- Mealy-Maschine konstruieren, die eine Dualzahl einliest und als Zweierkomplement wieder ausgibt. Die Aufgabe war aber nicht erklärt, man musste also wissen, wie das Zweierkomplement gebildet wird. Die Aufgabe gibt´s auch in den Heften.
- Kontextfreie Grammatik erstellen für 1^2m 0^m. m >=0. Dann daraus noch ein Wort ableiten.

Komplexaufgaben

Komplex 1:
- NEA mit Potenzmengenkonstruktion in DEA umwandeln. Graphen und Automatentafel.
- DEA vereinfachen. Verfahren frei wählbar.

Komplex 2:
- Produktautomat erstellen mit den Eigenschaften: Wörter, die das Teilwort 01 aber nicht das Teilwort 00 enthalten.
- Den Produktautomat erstellen, zeichnen und dann noch optimieren (z. B. mit dem Markierungsalgorithmus).
- Rechtslineare Grammatik für den Produktautomat angeben.
- Automat war gegeben. Regulären Ausdruck daraus berechnen. Hier war explizit das Verfahren aus den Heften verlangt. Also Gleichungssystem aufstellen und dieses lösen.

Komplex 3:
- Kellerautomat
- Kontextfreie Grammatik in Chomsky Normalform bringen

Die Prüfung war sehr fair und auf jeden Fall machbar.
Antworten