Typen von Grammatiken
kontextsensitiv falls für alle Regeln w1 -> w2 gilt: |w1| ? |w2| (|w|: Anzahl der Variablen und Terminalzeichen von w)
kontextfrei falls für alle Regeln w1 -> w2 gilt: w1 aus V
regulär falls zusätzlich gilt: w2 Terminalzeichen oder Terminalzeichen gefolgt von Variable
durch Grammatiktypen erzeugbare Sprachen bilden echte Teilmengen
kontextsensitive Sprachen
rekursiv aufzählbare Sprachen
durch beliebige Grammatiken erzeugbar