engl.: context-free grammar

Seien T und N zwei disjunkte Alphabete. Die Elemente von T nennen wir Terminalsymbole, die von N Nichtterminalsymbole.

Sei ⊓ eine endliche Teilmenge von N × (N ∪ T )* ; die Elemente von ⊓ heißen Produktionen oder Regeln.

Sei S ∈ N; S heißt Startsymbol oder Axiom. Dann heißt Γ = (N, T , Π, S) eine kontextfreie Grammatik, kurz kfG.

• Mit kfGn lassen sich genau die Sprachen definieren, die man auch mit Syntaxdiagrammen definieren kann.