Pour construire des ensembles de mots, on utilise la notion de grammaire. Une grammaire 
comporte deux alphabets 
et
, un axiome 
qui est une lettre appartenant à
et un ensemble 
de règles.
est dit alphabet terminal, tous les mots
construits par la grammaire sont constitués de lettres de .
est dit alphabet auxiliaire, ses lettres
servent de variables intermédiaires servant à engendrer des mots.
Une lettre de , appelée axiome, joue un rôle particulier.
où 
est une lettre de et 
un mot comportant des lettres
dans 
.