Tipps zu Blatt 1

Die Tipps sollten sinnvoll und richtig sein, eine Gewähr dafür übernehme ich aber nicht ;-)

Das Blatt ist sehr umfangreich!
Fangt sofort mit dem Lösen an, Montag reicht Euch garantiert nicht...
Ich war gut beschäftigt heute...

Gesucht ist die jeweilige Grammatik. Gebt mir also bitte das vollständige Quadrupel an und nicht nur die Produktionen.
Das finden von den Grammatiken ist neu für Euch. Deshalb wird es etwas dauern, bis Ihr die findet.
Deswegen löst das Blatt nicht alleine; mehrere Leute haben mehrere Sichten und Vorgehensweisen - so seid Ihr schneller...
ich hab' alleine lange gebraucht...

Bei den natürlichen Zahlen gehen wir davon aus, dass sie bei 0 beginnen... a^0 ist also z.B. Element von der ersten Sprache...

Die Antwort auf die Frage, welchen Chomsky-Typ die Grammatiken haben ist zwar (da Ihr die Grammatik ja angebt) immer 0 (weil die anderen 1,2,3 ja darin enthalten sind); die Antwort ist natürlich aber immer der größtmögliche Typ; bei der ersten also z.B. drei, wenn Ihr die Grammatik entsprechend aufbaut - was geht... (Keine der gesuchten Grammatiken ist Typ 0, insbesondere kommt man mit unter fünfzehn Regeln bei jedem Teil aus, von denen einige einander sehr ähnlich sind. Wenn Ihr also schon zu viele Regeln habt überlegt lieber nochmal von weiter vorne, wo es einfacher gehen könnte, sonst durchschaut Ihr Eure Regeln auch nicht mehr.)

- Die erste hatten wir mehr oder weniger schon auf Blatt 0 (F->a wird zu...)
- Die dritte ist etwas knifflig... Ihr habt sie aber wohl schonmal gesehen... wenn Ihr sie von da wo Ihr sie gesehen habt übernehmt, überlegt Euch aber, warum sie funktioniert (Umsortieren)...
- Bei der vierten und fünften bedeutet {a,b}* = {a,b} o {a,b} o {a,b} o {a,b} o ..., also einfach beliebig Elemente von {a,b} -also a's und b's- hintereinander. In vier sind das also alle Wörter über {a,b} beliebiger Länge, die gleich viele a's wie b's enthalten.

(Ihr habt nur zwei Dinge:
Variablen: Großbuchstaben
Terminalsymbole: Kleinbuchstaben

Wie der Name schon sagt sind Variablen etwas von dem aus es weiter geht, die man also in einer weiteren Regel durch irgend etwas ersetzen kann...
Terminalsymbole sind terminal, also fertig, die bleiben stehen und verändern sich in weiteren Regeln (auch Typ 1) nicht mehr...
Zum Ziel kommt Ihr meistens nur über Umwege...)


Vielleicht hilft noch ein Beispiel:
Ich suche {x aus {0,1}* | x enthält das Teilwort 010}.
Was tue ich?
Ich beginne mit S->? hmm, da soll 010 drin sein und aussenrum irgendwas, also vielleicht S->A010A.
Jetzt muss A nur noch irgendwas aus {0,1}* werden können, also A->AA, A->0, A->1.
Fertig...
Lösung: G=({S,A},{0,1},{S->A010A, A->AA, A->0, A->1} und das ganze ist vom Typ 2 - kontextfrei.

Hui, das sieht erstmal unmöglich aus...
die entscheidende Frage, die Ihr erstmal beantworten müsst, steht jedoch in der Bedingung:
"...Dezimaldarstellung von 1/7 hinter dem Komma"...

Welche Aneinanderreihung von Zahlen ist also möglich?
Wie bilde ich die auf eine Grammatik ab? Wer kommt nach wem?

Wo geht es los?
Was kann ich bauen? (alle Möglichkeiten...)
Gibt es da ein Problem?

Da ist erstmal der Doppelpfeil... damit ist auch etwas über n ungerade <=> ? ausgesagt...
Wie mache ich aus einer geraden Zahl eine ungerade?

Was heisst reguläre Grammatik? Regeln haben nur die Form A->a oder A->aA.

Wer keine Typ 3 Grammatik hinbekommt kann auch "nur" eine kontextfreie Grammatik bauen.
(Tip dazu: Bringt es vielleicht etwas, eine Sprache mit gerader Anzahl von Nullen und einsen zu bauen?)

Müsst Ihr nicht vorrechnen, könnt Ihr aber mal durchlesen und eine Sekunde darüber nachdenken. Da die Definition von kontextfrei aus dem Schöning anscheinend der von monoton entspricht, kann man da nicht allzu viel machen...

Schaut Euch die Grammatik an, baut ein paar Wörter, dann seht Ihr was...
Überlegt Euch, was ihr zeigen wollt.
Was heisst {a^2*n | n aus nat. Zahlen} ist Teilmenge von L(G) für die Elemente von {a^2*n | n aus nat. Zahlen}?
Was ist Eure Variable für die Induktion?

Viel Erfolg beim Lösen!

© marc-oliver pahl