Seminar 26./28. 11.

Aufgaben zu Grammatiken

$$Id: aufgaben.tex,v 1.1 2003/12/03 11:51:10 joe Exp $$

Sprachen (und ihre Komplemente Com*):

• Pali: $\{ w \mid w = \operatorname{reverse}(w) \}$
• Gleich: $\{ w \mid d(w) = 0 \}$, wobei $d(x) := \vert w\vert _a - \vert w\vert _b$
• Dyck-Sprache (korrekt geklammerte Wörter):

  $\{ w \mid d(w)=0 \wedge \forall u \sqsubseteq w: d(u)\ge 0 \},$

Aufgaben: G: finde CF-Grammatik, Ein: eindeutige CF-Grammatik

• empfohlen: Ein-Pali, G-ComPali, Ein-Dyck, G-ComGleich
• Highscores: Ein-(Com)Gleich, {G,Ein}-Com{Pali,Dyck}