Grammatik sodass L(G)=L

Question

Guten Tag,

noch eine Frage bezüglich das Angeben von Grammatiken.

Ich finde es einfacher aus einem Automat, die Grammatik zu konstruieren aber manchmal ist ´der Automat nicht vorgegeben, kompliziert herzustellen oder in der nächste Frage als Antwort zu geben.

Meine Frage ist:

Gibt es eine ''Strategie''/ Vorgehensweise um die Grammatik  zu konstruieren oder versucht man mit Bspielwörter nur.

Zum Beispiel habe ich die Lösungen von Aufgabe 30 und 31 (REC-AB und REC-AC) verstanden, ich konnte aber die nicht selbst lösen.

Answer 1

Man braucht dafür vor allem viel Übung. Es gibt für einzelne Grammatiktypen so ein paar Standard-Vorgehensweisen:

• Grammatiken vom Typ 3 werden im Prinzip genauso wie endliche Automaten konstruiert. Da kann man sich wirklich jedes Nonterminalsymbol wie den Zustand eines EAs vorstellen und sich so durch die Produktionen hangeln. Produktionen, die auf $\lambda$ gehen, entsprechen dabei Endzuständen. (Siehe auch Lehrbuch, Seite 188, zur Sprachmächtigkeit rechtslinearer Grammatiken.)
• Kontextfreie Grammatiken können schon deutlich komplexere Strukturen erzeugen, ein typisches Konstrukt dabei sind aber Regeln von diesem Typ:
  $X \rightarrow AXB$
  Sie erzeugen so eine geschachtelte "Klammerstruktur", wenn man sich $A$ als Klammer-Auf vorstellt und $B$ als Klammer-Zu. Man kann das auch mit anderen "Klammertypen" $C$ und $D$ kombinieren - das wird vor allem zum Parsen von Programmiersprachen oft benötigt. Eine zweite typische Struktur ist:
  $Y \rightarrow AYA | BYB$
  Auf diese Weise erhält man Palindrom-artige Wörter.
• Bei monotonen Grammatiken schließlich ist eine typische Vorgehensweise, dass man zweistufig
  • zuerst die richtige Anzahl an Zeichen erzeugt
  • und danach die Zeichen an die richtige Position sortiert.

Das sind natürlich nur einige wenige Möglichkeiten bei der Grammatik-Konstruktion - je kleiner der Grammatik-Typ ist, desto mehr kann man damit machen. Schon monotone Grammatiken sind so mächtig, dass man sich kaum Sprachen vorstellen kann, die durch sie nicht definiert werden können (und bei allgemeinen Grammatiken sind dann der Phantasie (fast) keine Grenzen gesetzt). Es ist also wichtig, dass Sie viel üben, um routiniert mit Grammatiken umgehen zu können! Aber die obigen Standardstrukturen sind schon einmal ein guter Einstieg - viel darüber hinaus machen wir in der Vorlesung ja auch nicht...

Aber überlegen Sie bspw. mal, wenn Sie diese Standardstrukturen schon gut beherrschen, wie eine monotone (oder meinetwegen auch allgemeine) Grammatik für die Sprache der Wörter vom Typ $$a^nb^{2^n}$$ aussehen könnte. Das ist gar nicht so leicht, aber man lernt viel dabei. (Ich glaube, wir haben in irgendeiner Übungsaufgabe auch die Lösung dafür.)

Comments

Vielen Dank für Ihre schnelle und ausführliche Antwort !
Ja es ist sehr ähnlich zu SAA-1-3.
Hier würde ich so machen : Man braucht eine kontextfreie Grammatik mit P= { S'--> S| lambda,
       S --> ABB|ASBB,
       A --> a,
       B --> b}

---

oder einfach {S--> ASBB|lambda,
                   A-->a,
                   B-->b}
Kommt darauf an welcher Grammatiktyp verlangt wird.

---

Da fehlen Ihnen aber noch die $c$'s...

---

Das war die Antwort für die Sprach a hoch n b hoch 2n

---

Nicht $a^nb^{2n}$, sondern $a^nb^{2^n}$. Das ist ein großer Unterschied!

Wichtiger Tipp für die Klausur (ganz im Ernst): LESEN Sie die Aufgaben genau durch! So viele Punkte gehen verloren, weil Leute die Aufgaben falsch verstanden haben.

---

Hallo,

Sie haben Recht.
Hier ist ein Versuch von mir bzgl a hoch n b hoch 2 hoch n;
Diese ist aber keine monotone Grammatik wegen Lambda:
{S-->KXBY,
 K-->aK|lambda,
 X-->XD|lambda,
 DY-->Y,
 Y-->lambda,
 DB-->BBD,
 B-->b}

Ich bedanke mich

---

Auf den ersten Blick sieht diese Grammatik gar nicht so schlecht aus - aber wenn man sie in den XWizard eingibt, kommen doch viele falsche Wörter heraus: http://www.xwizard.de:8080/Wizz?template=ID-C22148

Vielleicht schaffen Sie es ja noch, sie zu korrigieren?

---

Geben Sie aber bitte zum Herumprobieren in den declarations eine kleinere "maxdepth" ein (vielleicht 10 oder so).