Una gramàtica incontextual (CFG, Context Free Grammar) és un conjunt de regles de substitució on les parts esquerres són mots de longitud 1. Aquestes regles les anomenarem produccions i les seves parts esquerres variables (o no-terminals). Els símbols restants els anomenem terminals. Dues regles com per exemple i es poden representar de forma agrupada de [...]

Un alfabet () és un conjunt finit d’elements (símbols), habitualment caràcters alfanumèrics. Un mot és una llista de símbols d’un alfabet. El mot buit (llista de longitud 0) el denotarem amb el meta-símbol . Utilitzarem , , , , … per denominar paraules. Paraules: ab, bbb, a, Longituds: |ab|=2, |bbb|=3, |a|=1, ||=0 Extenem la notació [...]