Hallo, ich habe gerade ein Problem mit den FGI Aufgaben. Da wie immer die Vorlesung und das Skript nicht sehr viel hilft und wir in den Übungen nicht zu diesem Thema gekommen sind.

Kann mir vielleicht jemand helfen, indem er mir sagt wie man vorgehen muss wenn man zu einer Sprache eine passende Grammatik bilden will?

Wie macht ihr das? Oder vielleicht gibt es ja auch Erklärungshilfe zu Grammatiken von höheren Semestern. Würde mich freuen. Danke! :)

Zuerst solltest du dir überlegen was für eine Sprache du erzeugen möchtest:
regulär, kontextfrei,…

Bei den Aufgaben geht es um um kontextfreie Sprachen:

Diese kannst du durch eine kontextfreie Grammatik erzeugen.
Die definition einer Grammatik solltest du im Skript finden.

Das wichtige an den kontextfreien Grammatiken ist die Art wie die Produktionregeln,
also die Ableitungsvorschriften definiert werden müssen.

Definition einer Kontextfreien Grammatik nach Chomsky:

Eine Grammatik ist kontextfrei , falls für alle Regeln w1 –> w2 in den Produktionen
gilt: w1 ist eine einzelne Variable

D.h. also
Auf der Linkenseite einer Ableitung muss immer genau eine Variable bzw. ein Nonterminal stehen.

Wenn du z.B jetzt die Sprache (ab)^n (ba)^n mit n>0 erzeugen willst kannst du dies mit folgenden regeln hinbekommen.

S -> A
A -> abAba
A -> epsilon (leeres Wort)

Wobei a und b temrinale sind und A eine variable und S startsymbol.

Hierbei siehst du auch dass auch rekursive Konstrukte erstellen kannst.
Ein gutes Beispiel für Kontextfreie Grammatiken und deren Mächtigkeit ist
beispielsweise die BNF. Sollte in Se1 vorgekommen sein…

So ne kurzen Definition bzw. kurze Erklärungen findest du auch im Buch:
Theoretische Informatik Kurzgefasst - Uwe Schöning
Jedoch ist die Syntax die Schöning in dem Buch benutzt etwas abweichend von dem was
Prof Habel verwendet.

Vielen Dank schonmal :)

Ich finde es immer einfacher die Worte von anderen Studenten zu verstehen. Danke für die gute Erklärung :)