0 Daumen
938 Aufrufe

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 = {0n| n ≥ 3},

(b) L2 = {0m1n| m, n ≥ 2},

(c) L3 = {0m1m2n| m, n ≥ 1}.

Avatar von

1 Antwort

0 Daumen
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| ∅



Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community