Eine Chomsky-Grammatik G wird gegeben durch 4 Komponenten (N, T, P, S):

• T = eine endliche Menge von Symbolen, genannt Terminalsymbole.
• N = eine endliche Menge von Hilfsbegriffen , genannt Nichtterminalsymbole.
• P = eine endliche Menge von Produktionen oder Regeln,
• S N, das Startsymbol.

Wir verlangen: NT = Ø, und es ist praktisch, V = NT als Vokabular einzuführen (unsere Bezeichnungsweise entspricht dem Standard; im Lehrbuch "Skriptum Informatik" steht es merkwürdigerweise anders).

Die Regeln in P werden in der Form (,) oder meistens geschrieben; dabei sind und nahezu beliebige Zeichenfolgen aus V*, aber in muß mindestens ein Element aus N vorkommen, also: V* N V* , V*.

Ein Ableitungsschritt xy xy ist ein Übergang von einer beliebigen Zeichenfolge xy aus V*, in der vorkommt, zur Zeichenfolge xy ; dabei ist eine Regel aus P.

Eine Ableitung S * w ist eine Folge von 0 oder mehr Ableitungsschritten, die bei S anfängt. Das Ergebnis w heißt eine Satzform (S ist also auch eine Satzform).

Ist eine Satzform w T*, enthält sie also kein Element von N mehr, so heißt sie ein Satz.

Die Menge aller Sätze , also der Zeichenfolgen aus T*,  die durch Ableitungen aus S erzeugt werden können, heißt die durch G erzeugte Sprache  L(G). Die Hilfsbegriffe aus N kommen also darin nicht mehr vor; L(G) kann in Sonderfällen sogar leer sein.

Es gibt Grammatiken von der Art, daß in einer Ableitung dieselbe Satzform mehrfach auftreten kann. Das ist nutzlos und unerwünscht; man kann die Grammatik stets so umformen, ohne die erzeugte Sprache zu verändern, daß dies nicht vorkommen kann, und wir nehmen an, dies sei geschehen. Dann hat jede Satzform eine Ableitung endlicher Länge, und man kann die möglichen Ableitungen systematisch so erzeugen, daß jede Satzform genau einmal gefunden wird. Dann wird erst recht jeder Satz gefunden: die Sprache L(G) ist aufzählbar.