結構歸納法（structural induction）

結構歸納法是用來證明「由一組規則所建造的每個物件都具有某性質」的方法，做法是檢查最小的物件，然後說明每條規則都保持該性質。想像一套樂高，你只能從少數幾種基本積木出發，並用少數幾個固定的動作把它們組合起來：若每塊基本積木都是紅的，且每個動作都讓東西維持紅色，那麼你所能建出的一切都是紅的。你從不檢視每一個可能的模型——你信任基底與步驟。

它把普通的數學歸納法（沿 0, 1, 2, … 往上數）推廣到那些「由基底情形堆疊而成」的東西：字串、正規表示式、剖析樹、文法。證明分兩部分。基底情形檢查該性質對起始零件成立（空字串，或單一符號的正規表示式）。歸納步驟假設該性質對較小的零件成立（歸納假設），並說明由它們經一條構造規則組裝出的任何東西也必然成立。涵蓋每條規則，你就涵蓋了每個物件，因為每個物件都能從基底經有限多步抵達。

這是一次性證明關於所有字串或所有表示式之事實的標準工具。要證明每個正規表示式都表示某個語言，你檢查基本正規表示式表示語言，再檢查「表示語言之正規表示式」的聯集、串接與 Kleene 星號仍表示語言。要證明關於每棵剖析樹的性質，你檢查單葉的樹，再對子樹假設成立，並驗證當一條規則把它們接在新的根之下時性質仍然存活。沒有歸納法，你會面對無限多種情形；有了它，一個有限的證明就把它們全部搞定。