在計算機科學中，在形式語言理論領域，經常使用各種字符串函數； 但是，所使用的符號與計算機編程所使用的符號不同，一些理論領域常用的函數在編程時很少使用。 本文定義了其中一些基本術語。

字符串是有限的字符序列。空字符串表示為 ε {\displaystyle \varepsilon } 。兩個字符串 s {\displaystyle s} 和 t {\displaystyle t} 的連接表示為 s ? t {\displaystyle s\cdot t} ，或縮短為 s t {\displaystyle st} 。與空字符串連接沒有區別： s ? ε = s = ε ? s {\displaystyle s\cdot varepsilon =s=\varepsilon \cdot s} 。字符串的連接是關聯的： s ? ( t ? u ) = ( s ? t ) ? u {\displaystyle s\cdot (t\cdot u) =(s\cdot t)\cdot u} 。

語言是一組有限或無限的字符串。除了常見的集合運算，如并集、交集等，連接可以應用于語言：如果 S {\displaystyle S} 和 T {\displaystyle T} 都是語言， 它們的串聯 S ? T {\displaystyle S\cdot T} 被定義為來自 S {\displaystyle S} 的任何字符串和來自 T {\displaystyle T} 的任何字符串的串聯集合，形式為 S ? T = { s ? t ∠ s ∈ S ∧ t ∈ T } {\displaystyle S\cdot T=\{s\cdot t\mid s\in S\land t\in T\} } .同樣，為了簡潔起見，連接點 ? {\displaystyle \cdot } 通常被省略。

任意長度的所有十進制數的集合是無限語言的一個例子。

字符串的字母表是特定字符串中出現的所有字符的集合。 如果 s 是一個字符串，它的字母表示為

Alph ? ( s ) {\displaystyle \operatorname {Alph} (s)}

一種語言的字母表 S {\displaystyle S} 是出現在 S {\displaystyle S} 的任何字符串中的所有字符的集合

令 L 為一種語言，令 Σ 為其字母表。 字符串替換或簡單的替換是一個映射 f，它將 Σ 中的字符映射到語言（可能在不同的字母表中）。 因此，例如，給定一個字符 a ∈ Σ，有 f(a)=La 其中 La ? Δ* 是字母表為 Δ 的某種語言。 此映射可以擴展為字符串，如

f(ε)=ε

對于空字符串 ε，和

f(sa)=f(s)f(a)

對于字符串 s ∈ L 和字符 a ∈ Σ。 字符串替換可以擴展到整個語言，因為

f ( L ) = ? s ∈ L f ( s ) {\displaystyle f(L)=\bigcup _{s\in L}f(s)}

常規語言在字符串替換下是封閉的。 也就是說，如果將一種正則語言的字母表中的每個字符替換為另一種正則語言，結果仍然是一種正則語言。類似地，上下文無關語言在字符串替換下是封閉的。