Einige Nachfragen

Question

erstmal: dass die Aufgabe leicht ist, ist mehr als relativ.

Aufg.a)

1)Es ist klar wie die Wörter von der Gramatik aussehen, und dass sie kontextsensitiv ist, aber wie komme ich darauf, dass sie rechtslinear ist. Und dann auch noch ohne Keller funktioniert?

2)Wir haben doch gelernt, dass zeichen im Keller gelöscht werden, und dann sieht man, dass die Sprache dazugehört. Wie sehe ich denn jetzt dass die Sprache dazugehört?

3)Man kann ja, wie es in der Lsg. steht, die Aufg. auch mit Keller löschen, wie wäre die Lsg. dann? Woher weiß ich wann das Löschen anfängt?

4)Bei der gegebenen Lösung: wo ist der Sinn, dass ich bei der Eingabe von b ständig denn zustand wechsel, soll es mir helfen den Umkehrpunkt zu finden?

 

Vielen Dank

 

Answer 1

1) Man kann sich zu der Sprache schnell einen endlichen Automaten vorstellen, der diese akzeptiert, da die Struktur der Sprache sehr einfach ist (eine EA ist ja quasi ein Kellerautomat, der den Keller nicht nutzt). Daher muss es auch eine rechtslineare Grammatik geben, die diese Sprache erzeugen kann.

2)Diese Frage verstehe ich leider nicht. Zu was soll die Sprache dazu gehören und wie soll das mit dem Löschen von Zeichen aus dem Keller zusammen hängen?

3)Man könnte zum Beispiel, wenn ein b gelesen wird, dieses in den Keller schreiben. Sobald dann das nächste b kommt, kann man das im Keller stehende b wieder löschen. Wenn dann das dritte b kommt geht das wieder von vorne los. Man wüsste dann, dass der Keller nur k0 enthalten darf, wenn das erste a kommt. Sonst würde das Wort nicht akzeptiert werden, da im ersten Teil der akzeptierten Wörter ja eine gerade Anzahl bs steht.

4) Das Wechseln der Zustände codiert, ob eine ungerade oder gerade Anzahl bs zum aktuellen Zeitpunkt eingelesen wurde. Dies muss erfolgen, damit der Automat nur in einen Endzustand gelangen kann, wenn nach einer geraden Anzahl bs die Zeichen aab kommen.

 

Answer 2

zu 1. Dass es hier eine rechtslineare Grammatik gibt und somit einen Kellerautomaten, der den Keller nicht nutzt, das müssen Sie hier nicht erkennen. Es war nur ein nichtdeterministischer Kellerautomat gefordert. Wenn Sie diesen anders (z.B. mit Verwendung des Kellers) konstruieren, und er richtig ist und  zu den Vorgaben der Aufgabenstellung passt, dann ist das ja auch in Ordnung.

zu 2. Ich gehe davon aus, dass Sie hier überprüfen wollen, ob ein Wort zu einer Sprache gehört, d.h. ob dieses von dem Kellerautomat akzeptiert wird (Akzeptor)? Ob ein Wort zu der gegebenen Sprache gehört oder nicht sieht man daran, ob der Kellerautomat nach Abarbeitung des Wortes in einem Endzustand ist oder nicht. ("Zeichen aus dem Keller löschen" hilft Ihnen beispielsweise die Anzahl von Zeichen zu zählen, vgl. a^nb^n, hilft Ihnen aber nicht zu erkennen, ob ein Wort zu der Sprache gehört oder nicht.)

zu 3. sobald hier das erste a kommt, sollten Sie den Zustand wechseln, um zu gewährleisten, dass nach dem a nur noch genau ein a (dann wäre im Keller genau ein a, welches wieder gelöscht werden könnte) und ein b (der Keller enthielte nur k0) kommt.

zu 4. dieses Kodieren der geraden / ungeraden Anzahl an b's können Sie, wie bereits beschrieben, auch mit Hilfe des Kellers erreichen.

Freundliche Grüße
Friederike Pfeiffer