5Weitere strukturelle Eigenschaften der vorgestellten Sprachklassen

Die Sprachklassen L0 bis L3, welche zu den Automaten- und Grammatiktypen gehören, die wir in den vorausgegangenen Kapiteln erarbeitet haben, gehören zur Chomsky-Hierarchie (den exotischen Typ 4 werden wir im Folgenden außer Acht lassen). Sie stehen zueinander in Teilmengenbeziehungen, wobei jeweils die Klassen mit höherer Zahl echte Teilmengen jeder der Klassen mit niedrigerer Zahl sind.

Beachten Sie aber, dass auf struktureller Ebene der Grammatiken diese Teilmengenbeziehung nicht immer gilt. Wie wir gesehen haben, sind beispielsweise nicht alle kontextfreien Grammatiken monoton ...

Get Theoretische Informatik - ganz praktisch now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.