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 u w : d (u)0},
Aufgaben:
G
: finde CF-Grammatik,
Ein
: eindeutige CF-Grammatik
Ein-Pali, G-ComPali, Ein-Dyck, G-ComGleich
Ein-(Com)Gleich, {G,Ein}-Com{Pali,Dyck}