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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
