Aufg 31 a), REC-AC

Question

Ich habe für die Produktionsmenge folgende (einfachere) Lösung. Ist diese richtig und wenn nein, warum nicht?

P: { S -> 0 | 0S | 1A, A -> 1 | 1S }

Vielen Dank!

Answer 1

Hallo,

deine Produktionsmenge ist leider nicht ganz richtig. Wenn du zum Beispiel folgendes machst:

S -> 1A -> 11S -> 110 . Dies ist in deiner Produktionsmenge erlaubt. Allerdings ist 110 nicht in unserer Sprache L enthalten, da eine Eins vorkommt, aber die Zeichenfolge 1100 nicht. Du musst deshalb mehr Nonterminalsymbole einführen, um diesen Fall auszuschließen.

Viele Grüße,

Julia (Tutorin)