Alternative Lösung 49)a

Question

Wäre auch folgende Grammatik gültig?

S-> aBa /bBb

B-> bbC / aaD

C-> bbE/ aaE

D-> aaF/bbF

E-> bb

F-> aa

Danke!

Comments

Können Sie diese Grammatik bitte als XWizard-Skript posten? Sie erleichtern uns damit die Beantwortung.

Answer 1

Hallo,

zugegeben funktioniert deine Grammatik natürlich für das Testwort abbaabba aus Aufgabenteil b).

Allerdings ist die durch deine Grammatik entstehende Sprache nicht äquivalent mit der gesuchten, dazu folgendes Testwort:

ababbaba (ist in der Sprache der acht Zeichen langen Palindrome erhalten)

Folgender Ablauf:

S -> aBa -> abbCa oder aaaDa (siehe zweite Regel der Grammatik)

Hier wird schon klar, dass das obige Wort nicht mehr zu bilden ist, da z.B. zwischen den ersten zwei a's kein Nonterminalzeichen mehr existiert, welches zu einem b umgewandelt werden könnte.

Ich hoffe das Problem wird klar, so bildet die Grammatik zwar einzelne Testwörter ab, sie stellt jedoch keineswegs die gesuchte Sprache dar.

Gruß

Max (Tutor)