So, jetzt habe ich auch mal ein paar GThI-Fragen, und zwar zur Klausur vom letzten Semester (16.02.2010) (kommt mir das nur so vor, oder ist die tatsächlich deutlich abgedrehter als die Klausuren der Jahre zuvor?)
Aufgabe 2
Geben Sie einen deterministischen endlichen Automaten M an, für den gilt:
ist die Binärdarstellung (evtl. mit führenden Nullen) einer Zahl
, die durch 3 teilbar ist
Ich scheitere bereits daran, daß ich keinen Plan davon habe, wie eine durch 3 teilbare Zahl in Binärdarstellung überhaupt aussieht. In Dezimaldarstellung ist es klar: die Quersumme ist durch 3 teilbar. Aber binär? Ich habe mir mal die entsprechenden Zahlen bis 24 aufgeschrieben, kann da aber auch keinerlei System entdecken.
Mit Google finde ich folgende Produktion: N -> 11 | 1001 | N0 | NN
Abgesehen davon, daß ich mich auch hier wieder frage "Wie kommt man darauf?" ist das ja zudem noch eine Typ2-Grammatik, hilft auf der Suche nach einem DEA also auch nicht weiter.
Aufgabe 4
Sei
mit
.
a) Von welchem Typ ist die Grammatik G?
b) Von welchem Typ ist die Sprache L(G)?
Begründen Sie Ihre Antworten!
Irgendwie verstehe ich hier die Frage nicht. Klar, die Grammatik ist vom Typ 2: rechte Seiten der Produktionen sind mindestens genauso lang, wie die linken Seiten der Produktionen, linke Seite der Produktionen sind einzelne Variablen (würde das als Begründung schon ausreichen?)
Aber was wird jetzt bei Teil b erwartet? Selbst im Skript wird mal von Typ-i-Grammatik und mal von Typ-i-Sprache geredet, bzw. z.B. von kontextfreier Sprache und kontextfreier Grammatik. Wo ist hier also der Unterschied?
Aufgabe 5
Geben Sie eine kontextfreie Grammatik G an, für die gilt:
L(G) ist also die Sprache aller Wörter w, für die gilt, dass jedes Präfix von w mindestens so viele 0en wie 1en enthält.
Gibt es hier irgendwie eine systematische Heransgehensweise? Ich habe hier zwar durch (zu langes) Herumprobieren eine Grammatik gefunden, wobei ich mir aber nicht wirklich sicher bin, ob sie wirklich korrekt ist ...
So weit bin ich:
sowohl w, als auch u und v scheinen ja aus dem leeren Wort bestehen zu können, daher als Start folgendes (A sorgt dann für die Produktionen des Präfixes, E für das Suffix):
S ->
| AE | A | E
Das Suffix ist dann beliebig:
E -> 0 | 1 | 0E | 1E
Beim Präfix wird's dann sehr vie komplizierter
die 0 kann beliebig oft und an beliebiger Stelle erzeugt werden:
A -> 0 | 0A | A0
wenn eine 1 kommt, dann brauchen wir eine Variable, die uns sagt, wir brauchen auch eine 0 dazu:
A -> 1B|B1
B -> 0 | 0A | A0
und danach geht das Spiel wieder von vorne los ...
Keine Ahnung, ob die wirklich so korrekt ist ...
Fragen über Fragen, ich hoffe, es kann irgendjemand Licht ins Dunkle bringen ...
Viele Grüße
Carsten