圖與樹（graphs and trees）

圖是一張描繪「東西」與「東西之間連結」的圖畫：用點（稱為頂點或節點）以線（稱為邊）相連。地鐵路線圖、交友網絡、流程圖——全都是圖。當連結帶有方向（單向箭頭）時，我們就有了有向圖。這正是你為有限自動機畫的那張圖：每個狀態是一個節點，每個轉移是一支從某節點指向另一節點、帶標籤的箭頭。

形式上，有向圖是一個頂點集合 V 連同一個邊的集合，每條邊是一個有序對 (u, v)，畫成從 u 指向 v 的箭頭。路徑是一連串可以順著箭頭依序走過的邊，迴圈則是繞回起點的路徑。樹是一種特殊的圖，沒有迴圈，且任兩個節點之間恰有一條路徑：它有一個唯一的頂端節點稱為根，其他每個節點恰有一個父節點，沒有子節點的節點叫葉。對於任何一再分岔卻從不重新合併的東西，樹是最自然的形狀——家譜、資料夾階層，或一個句子的結構。

這兩張圖畫撐起了這門學科裡大部分的圖示。自動機的狀態圖就是一張有向圖，而問「這個輸入能不能把機器從起始狀態推到接受狀態？」就是在問某條特定路徑是否存在。剖析樹展示文法如何推導出一個字串，根部是起始符號，文法規則向下分岔，真正的字串則由葉子從左到右讀出；後面要講的結構歸納法，正是藉由從葉子往上層層建立來證明關於所有這類樹的事實。