Aufgaben zu Grammatiken

Id: aufgaben.tex,v 1.2 2005/11/02 23:37:52 waldmann Exp

Sprachen (und ihre Komplemente Com*):

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

  {w | 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}