Potentielle Fehler im Lehrbuch 'Theoretische Informatik - ganz praktisch'

Question

Guten Abend,

ich bin der Meinung, einige Fehler im Buch entdeckt zu haben.

- Der auf Seite 130 angegebene nichtdeterministische endliche Automat für die Sprache L-mod würde das leere Wort 'lambda' fälschlicherweise nicht akzeptieren, obwohl das leere Wort laut Sprachdefinition auf Seite 36 Teil der Sprache ist. Folglich sollte der Anfangszustand s0 in die Endzustandsmenge aufgenommen und im Zustandsdiagramm entsprechend gekennzeichnet werden.

- Auf Seite 140 unten steht: 'In der Art, wie sie Sprachen definieren, verhalten sich SPRACHEN und Grammatiken in gewisser Weise komplementär zueinander.' Hier sollte statt Sprachen, Automaten stehen.

- Die auf Seite 184 angegebene rechtslineare Grammatik für die Sprache L-mod berücksichtigt die Möglichkeit der Erzeugung des leeren Wortes ebenfalls nicht. Hier sollte nämlich zusätzlich eine Produktion S--> 'lambda' hinzugefügt werden, um das leere Wort, welches ja in der Sprache enthalten ist, erzeugen zu können.

- Auf Seite 188 steht: 'Diese Beobachtungen können genutzt werden, um zu beweisen, dass die Klasse der von KONTEXTFREIEN Grammatiken erzeugbaren Sprachen genau die Klasse der von endlichen Automaten erkennbaren Sprachen ist.' Hier sollten die kontextfreien Grammatiken durch die rechtslinearen Grammatiken, welche ja bezüglich der Sprachdefinition äquivalent zu den endlichen Automaten sind, ersetzt werden.

- Auf Seite 190 steht: 'Für diese Stufe, die trotzdem „vierte Stufe der Chomsky-Hierarchie“ genannt wird (da bei 0 zu zählen begonnen wurde, sind es dann also insgesamt fünf Stufen) werden die Produktionen so weit eingeschränkt, dass nur noch solche erlaubt sind, die auf der rechten Seite ausschließlich NICHTTERMINALZEICHEN enthalten:' Hier sollte Terminalzeichen statt Nichtterminalzeichen stehen.

- Ich meine, dass sich die auf Seite 235 dargestellte Grammatik aufgrund der lambda-Regel nicht in KNF befindet, da S auf lambda gehen kann, obwohl S auf einer rechten Seite auftaucht.

 

Es kann natürlich sein, dass ich an der ein oder anderen Stelle falsch liege.

Answer 1

Vielen Dank für die Hinweise (obwohl ich hoffe, dass sie hin und wieder falsch liegen...)!

Ich werde mir das morgen mal anschauen und Ihnen bescheidgeben, ob Sie recht haben.

Auf jeden Fall finde ich es sehr gut, dass Sie sich so gründlich mit den Büchern beschäftigt haben.