Nechť Σ je abeceda.
Formální jazyk L nad Σ: L ⊆ Σ* (Množina řetězců).
Množina L nám umožňuje používat běžné množinové operace jako je sjednocení, průnik, rozdíl, komplement. Důležitou operací je zřetězení.
Operace zřetězení:
∀ x,y ∈ Σ∗, připojením řetězce y za řetězec x vznikne řetězec x.y
Slova můžeme generovat gramatikou G:
L(G) = {w : w ∈ Σ*, S ⇒* w} je jazyk generovaný gramatikou G = (N,T,P,S).