Operation auf Wörtern über einem endlichen Alphabet Σ, die jeden Buchstaben des Argumentwortes durch ein nichtleeres Wort ersetzt.

τ ist eine ϵ-freie Substitution, falls es eine Abbildung τ′ : Σ ↦ Σ* gibt mit τ′(x) ≠ ϵ für alle x ∈ Σ und \begin{eqnarray}\tau ({a}_{1}{a}_{1}\ldots {a}_{n})={\tau }{^{\prime}}({a}_{1}){\tau }{^{\prime}}({a}_{2})\ldots {\tau }{^{\prime}}({a}_{n})\end{eqnarray} sowie τ(ϵ) = ϵ.

Die Operation kann zu einer Sprachoperation erweitert werden, indem \begin{eqnarray}\tau (L)=\{\tau (w)|w\in L\}\end{eqnarray} gesetzt wird.