對同態的封閉性（closure under homomorphism）

同態（homomorphism）是一條對符號的「尋找並取代」規則。你為字母表的每個字母固定一個要替換成的字串，然後把這個替換按順序套用到字串的「每一個」符號上，再把結果黏接起來。把 a 換成 01、把 b 換成空字串 ε（epsilon），就把 aba 變成 01 01，也就是 0101。它只是一種逐符號的系統化翻譯。

形式上，同態 h 把字母表 Σ（Sigma）的每個符號送到某個（可能不同的）字母表上的一個字串，並透過 h(s1 s2 ... sn) ＝ h(s1) h(s2) ... h(sn) 延伸到整個字串，且 h 對空字串的值為空。對一個語言 L，其像 h(L) 是 { h(w) : w 屬於 L }——把語言裡每個字串都翻譯一遍。封閉性的主張是：若 L 是正規語言，則 h(L) 也是正規語言。構造很直接——在 L 的正規表示式中，把每個符號 x 的每次出現替換為 h(x) 的正規表示式，所得結果就表示 h(L)。（對「反同態」h^{-1}(M) ＝ { w : h(w) 屬於 M } 也封閉，這在自動機上證明。）

同態是讓你跨字母表重複利用既有結論的橋梁，也是一把鋒利的非正規性工具。因為正規語言對同態封閉，所以若對某候選語言施加或反施加一個同態會產生「已知非正規」的語言，那這個候選語言也不可能是正規的。要注意：一個符號可以映成多符號字串、也可以映成 ε，因此同態能拉長、縮短、甚至抹去字串的某些部分——它「不只是」一對一的改名。