Grammatik-Typen in der Chomsky-Hierarchie

Question

Geben Sie für die folgenden drei Sprachen jeweils möglichst einfache Grammatiken an und ordnen Sie den Grammatiken den jeweiligen Typ zu (d. h., ordnen Sie diese drei Sprachen in möglichst kleine Klassen der Chomsky-Hierarchie ein).

(a) L1 = {0ⁿ| n ≥ 3},

(b) L2 = {0^m1ⁿ| m, n ≥ 2},

(c) L3 = {0^m1^m2ⁿ| m, n ≥ 1}.

Answer 1

Für a:

Es ist die Sprache der Zeichenketten die nur 0s enthalten, und es fängt mit 000 an.Also die Regel mit der du anfängst muss das 000 enthalten, denn es gibt keine keine Zeichenkette die nicht mit 000 anfängt.  Aber die Regel kann nicht dort aufhören denn 0000 ist auch zum Beispiel gültig.

Die Grammatik sollte folgenderweise aussehen:


A->000S 
S>0S| ∅