NACLO考題分析（2007–2026）× 計算語言學互動入門
NACLO 每年設 Open Round（公開賽，約 8–10 題）與 Invitational Round（邀請賽，約 5–8 題，難度更高）。根據 2007–2026 年共約 280+ 道題目，可歸納為九大類型。
提供未知語言的句子與對譯，要求歸納形態規則後翻譯新句。涵蓋南島語族、北美原住民語、非洲語言、高加索語言等。
古文字解讀、非拉丁文字對應、人造書寫系統。核心是 pattern recognition 與符號─音韻對映推理。
FSA/FST、Huffman 編碼、DAWG、CFG/CCG、edit distance、密碼學、邏輯推理。這是 NACLO 區別於 IOL 的標誌性特色。
近年新增：attention 可視化、word embeddings 空間分析、LLM 錯誤模式辨識、機器翻譯後編輯等。
| 知識領域 | 具體考點 | 頻率 |
|---|---|---|
| 形態學 | 黏著 vs 屈折、詞綴切分、重疊、名詞類別、動詞一致性、領屬標記 | ★★★★★ |
| 音韻學 | 元音和諧、輔音交替、聲調、重音規則、音節結構、規則排序 | ★★★☆☆ |
| 文字學 | 字母、音節文字、語素文字、abugida/abjad 辨識；正寫法設計 | ★★★☆☆ |
| 句法學 | 語序類型、關係子句、格標記、一致性、ergativity | ★★★☆☆ |
| 語意學 | 詞義關係、evidentiality、TAM、真值條件、親屬稱謂 | ★★☆☆☆ |
| 語言多樣性 | 瀕危語言、polysynthesis、serial verbs、classifiers、pidgin/creole | ★★★★☆ |
| 計算能力 | 在 NACLO 中的表現 | 頻率 |
|---|---|---|
| 模式辨識 | 從平行語料歸納形態─語意對映規則 | ★★★★★ |
| 約束滿足 | 多重條件下找唯一合法對映（CSP） | ★★★★☆ |
| 遞迴與組合性 | 數詞乘加結構、嵌套關係子句 | ★★★☆☆ |
| 形式語言與自動機 | FSA/FST、CFG、Huffman、正規表達式 | ★★★☆☆ |
| 搜尋與回溯 | 密碼破解、Levenshtein distance | ★★☆☆☆ |
| 向量空間推理 | GloVe 幾何、attention 矩陣、LLM 偏差分析 | ★★☆☆☆ |
不完整翻譯對照表，多重形態規則交叉限制，消去法求解。
音韻交替以 FST 或 rewrite rules 呈現。
GloVe/WordNet 中推理詞義關係。
密碼破解 = combinatorial search + 音韻/形態約束。
每單元依循「類比 → 公式 → 互動模擬」三段遞進，為人文社會背景學生設計。
想像捷運站閘門——它只記得「目前在什麼狀態」（等待 → 已投幣 → 已通過），根據輸入決定下一步，沒有記憶、沒有計算器。這就是 FSA。若閘門在每次轉換時還輸出動作（印收據、亮燈），那就是 FST——語言學中用它描述音韻規則。
FST 擴展為 $(Q,\,\Sigma,\,\Gamma,\,\delta,\,\omega,\,q_0,\,F)$，多了輸出字母表 $\Gamma$ 和輸出函數 $\omega\colon Q \times \Sigma \to \Gamma^*$。
輸入土耳其語詞幹，後綴模板中的大寫 A 會根據詞幹最後元音的前/後特徵自動和諧。前元音 (e, i, ö, ü) → A=e；後元音 (a, ı, o, u) → A=a。
CFG 就像食譜——「一份沙拉 = 底菜 + 配料 + 醬汁」，而「底菜」可展開為「生菜 | 菠菜」。$\text{S} \to \text{NP}\;\text{VP}$ 是語言的食譜：句子拆成名詞片語和動詞片語。FSA 無法處理 $a^n b^n$（需記住出現次數），CFG 靠遞迴做到。
輸入由以下詞彙組成的中文句子。名詞：貓、魚、書、學生｜動詞：吃、讀、追｜限定詞：那、這
「接龍變字」遊戲：cat → cot → cog → dog，3 步。Levenshtein distance 就是最佳解——最少幾次插入、刪除、替換能讓兩字串互變。語言學中，拉丁語 pater → 西班牙語 padre 之間的「編輯」就是歷史音變。
輸入兩個字串，即時顯示 DP 矩陣與最優路徑（紅色標記）。
向外星人描述水果——用「甜度」和「酸度」兩個軸，在座標紙上標出位置。蘋果和梨靠很近，檸檬遠在酸的那端。Word embedding 做同樣的事，只是維度從 2 變成 50–300，座標從海量文本的共現統計學出。Firth (1957)：You shall know a word by the company it keeps。
點擊任意兩個詞，計算它們的餘弦相似度。顏色代表語意群組。
猜數字遊戲：1–100，用「是/否」問題猜，二分法最多 7 題（$2^7 = 128 > 100$）。熵衡量的就是「平均需要幾個二元問題才能確定答案」。Huffman 編碼是最優實現：高頻符號短碼，低頻長碼。自然語言天然如此——the 三字母，antidisestablishmentarianism 二十八字母。
輸入任意文本（英文或中文），自動計算字元頻率、Shannon 熵，並建構 Huffman 編碼表。
| 單元 | 核心概念 | 語言學連結 | NACLO 密度 | 時數 |
|---|---|---|---|---|
| 1. FSA/FST | 狀態、轉移、輸入─輸出轉寫 | 音韻規則、正寫法轉換 | ★★★★ | 3h |
| 2. CFG | 產生規則、遞迴、剖析樹 | 句法結構、Chomsky 層級 | ★★★ | 3h |
| 3. Edit Distance | DP 矩陣、對齊、加權成本 | 同源詞判定、音變模型 | ★★ | 2h |
| 4. Embeddings | 向量空間、cosine、類比 | 分佈語意、詞義關係 | ★★★ | 2h |
| 5. 資訊理論 | 熵、Huffman、冗餘 | Zipf、壓縮、perplexity | ★★ | 2h |
以下三題將真實的程式語言概念（stack machine、quotation、logic programming）包裝為「未知語言」，讓學生在零程式背景下體驗 NACLO 計算面向的題型。建議作答時間 90 分鐘。每題附有完整詳解與互動模擬器。
Koro 是一種未知語言，作用於一個序列（stack）。序列以 […] 表示，右端為頂端。元素可以是整數（如 3）、布林（T / F）、或子序列（如 {1 2}）。
| 編號 | 輸入 | 指令 | 輸出 |
|---|---|---|---|
| [A] | [4] | zaku | [4 4] |
| [B] | [3 8] | pilo | [8 3] |
| [C] | [2 5] | nari | [7] |
| [D] | [F T] | nari | [T] |
| [E] | [{1} {2 3}] | nari | [{1 2 3}] |
| [F] | [2 5] | motu | [10] |
| [G] | [{2 5} 9] | toro | [{2 5 9}] |
| [H] | [9 {2 5}] | toro | invalid |
| [I] | [100 200 T] | seku | [100] |
| [J] | [100 200 F] | seku | [200] |
| [K] | [T] | zaku nari | [T] |
| [L] | [3 4] | zaku nari | [3 8] |
| [M] | [3 4] | nari zaku | [7 7] |
zaku、pilo、nari、motu、toro、seku
[K] 與 [L] 結果不同；[L] 與 [M] 結果不同
[6] zaku nari[2 3 4] pilo nari[{1} {2}] nari zaku
① nari 永遠是加法 ② nari 的行為取決於輸入型別 ③ toro 對任何輸入都有效 ④ seku 只依賴最後一個元素 ⑤ pilo 不會改變元素內容
| 指令 | 功能 | 類比 | 推導依據 |
|---|---|---|---|
| zaku | 複製頂端元素（dup） | 影印機 | [A]: 4→4 4 |
| pilo | 交換頂端兩元素（swap） | 翻牌 | [B]: 3 8→8 3 |
| nari | 合併頂端兩元素（多型：整數=加法、布林=OR、序列=串接） | 黏合劑 | [C]+[D]+[E] 三筆交叉比對 |
| motu | 頂端兩整數相乘（mul） | 乘法器 | [F]: 2×5=10 |
| toro | 將頂端元素追加到下方序列尾端（snoc） | 排隊加人 | [G] vs [H]：需序列在下、元素在上 |
| seku | 依頂端布林從下方兩元素中選擇（T=較深者、F=較淺者） | if-then-else | [I] vs [J] |
[K] vs [L]：zaku 只複製頂端，nari 只作用於最頂端的兩個元素。
[K] [T] zaku → [T T]，nari(T,T) = T OR T = T → [T]
[L] [3 4] zaku → [3 4 4]，nari(4,4) = 4+4 = 8 → [3 8]
注意：nari 只消耗頂端兩個，底部的 3 不受影響
[L] vs [M]：指令順序不同，結果完全不同。
[L] [3 4] → zaku → [3 4 4] → nari → [3 8]（先複製再合併）
[M] [3 4] → nari → [7] → zaku → [7 7]（先合併再複製）
這體現了 stack 語言的核心特性：指令順序即程式邏輯。
[6] zaku nari → [6 6] → [12]
[2 3 4] pilo nari
pilo 交換頂端兩個：[2 3 4] → [2 4 3]
nari 合併頂端兩個：4+3 = 7 → [2 7]
[{1} {2}] nari zaku
nari 串接序列：{1}+{2} = {1 2} → [{1 2}]
zaku 複製：→ [{1 2} {1 2}]
| ① nari 永遠是加法 | ✗ | [D] 布林為 OR、[E] 序列為串接 |
| ② nari 的行為取決於輸入型別 | ✓ | 整數→加、布林→OR、序列→concat |
| ③ toro 對任何輸入都有效 | ✗ | [H] 順序錯誤即 invalid |
| ④ seku 只依賴最後一個元素 | ✗ | 選擇邏輯依賴布林，但結果取決於另外兩個元素 |
| ⑤ pilo 不會改變元素內容 | ✓ | 只交換位置，不修改值 |
答：② ⑤
語言學知識點：nari 的多型行為（polymorphism）對應自然語言中的一詞多義（polysemy）——同一個詞的意義隨上下文（此處為型別）而變。這也呼應了計算語言學中 type-driven semantics 的核心思想。
輸入 stack 初始狀態和指令序列，逐步觀察 stack 變化。指令：zaku pilo nari motu toro seku
Jex 是一種未知語言，其中 […] 表示一段「可被執行的內容」（quotation）。
| # | 程式 | 結果 |
|---|---|---|
| [1] | 4 dup | 4 4 |
| [2] | 3 8 swap | 8 3 |
| [3] | [2 5 add] run | 7 |
| [4] | 3 [dup add] run | 6 |
| [5] | [1 2] [dup concat] run | [1 2 1 2] |
| [6] | [dup] run | invalid |
| [7] | [3 dup] run | 3 3 |
| [8] | [dup dup add] run | invalid |
| [9] | 4 [dup dup add add] run | 12 |
dup、swap、add、concat、run
① [add] run ② [3 add] run ③ [dup add] run ④ 5 [dup add] run
[dup add] 在不同情況下結果不同？| 指令 | 功能 | 推導依據 |
|---|---|---|
| dup | 複製 stack 頂端 | [1]: 4→4 4 |
| swap | 交換頂端兩元素 | [2]: 3 8→8 3 |
| add | 頂端兩元素相加 | [3]: 2+5=7 |
| concat | 串接兩個 quotation | [5]: [1 2]+[1 2]=[1 2 1 2] |
| run | 取出頂端的 quotation 並執行其內容 | [3]–[9] 綜合推導 |
[6] [dup] run：run 取出 [dup] 並執行。此時 stack 是空的。dup 需要至少一個元素才能複製 → invalid（stack underflow）。
[7] [3 dup] run：run 取出 [3 dup] 並執行。先 push 3，stack 變 [3]；再 dup → [3 3]。quotation 自帶資料，所以不會 underflow → valid。
關鍵洞察：run 執行 quotation 時，quotation 可以存取外部 stack（如 [4]），也可以自帶資料（如 [7]）。但若 quotation 內的指令所需的資料既不在外部 stack 也不在 quotation 內部，就會失敗。
① [add] run | ✗ | stack 空，add 需要兩個元素 |
② [3 add] run | ✗ | quotation 內 push 3，但 add 仍需兩個元素（只有一個） |
③ [dup add] run | ✗ | stack 空，dup 就已失敗 |
④ 5 [dup add] run | ✓ | 外部 stack 有 5 → dup=5 5 → add=10 |
答：僅 ④
[dup add] 本身只是一段「程式碼」，不包含資料。它的行為完全取決於 run 執行時的 stack 語境：
• 空 stack + [dup add] run → invalid（無料可用）
• 5 [dup add] run → 5 dup = 5 5, add = 10
• 3 [dup add] run → 3 dup = 3 3, add = 6
• [1 2] [dup add] run → [1 2] dup = [1 2] [1 2], add → 型別錯誤？
語言學連結：這和自然語言中代詞的照應（anaphora）極為相似——「他跑了」中的「他」意義取決於前文語境。quotation 裡的 dup 就像一個代詞，它「指涉」的對象要到執行時才確定。這正是語用學中 context-dependence 的計算類比。
輸入程式碼（如 5 [dup add] run），觀察逐步執行過程。
Relka 是一種描述關係的語言。
par(ana, bo) par(ana, cy) par(bo, di) par(cy, el)
fem(ana) mas(bo) fem(cy)
mom(X,Y) :- par(X,Y), fem(X)
dad(X,Y) :- par(X,Y), mas(X)
sib(X,Y) :- par(Z,X), par(Z,Y)
anc(X,Y) :- par(X,Y)
anc(X,Y) :- par(X,Z), anc(Z,Y)
?- mom(ana, bo) → yes ?- dad(ana, bo) → no ?- anc(ana, di) → yes
par、:-、?-、anc
?- dad(bo, di)、?- anc(ana, el)、?- sib(bo, bo)
| 符號 | 意義 |
|---|---|
| par(X,Y) | X 是 Y 的親代（parent） |
| :- | 規則定義符（「若右邊成立，則左邊成立」），等同於邏輯蘊含 ← |
| ?- | 查詢符（「以下命題是否成立？」） |
| anc(X,Y) | X 是 Y 的祖先（ancestor），由兩條遞迴規則定義 |
?- dad(bo, di)
需要：par(bo, di) ✓ 且 mas(bo) ✓
→ yes
?- anc(ana, el)
嘗試規則 1：par(ana, el)？ 事實中沒有 → 失敗
嘗試規則 2：par(ana, Z), anc(Z, el)?
Z = cy：par(ana, cy) ✓，anc(cy, el)?
anc 規則 1：par(cy, el) ✓ → 成功！
→ yes（ana 是 el 的祖母）
?- sib(bo, bo)
sib(X,Y) :- par(Z,X), par(Z,Y)
X=bo, Y=bo, Z=ana：par(ana, bo) ✓, par(ana, bo) ✓
→ yes（！）
規則 sib(X,Y) :- par(Z,X), par(Z,Y) 只要求 X 和 Y 有共同的親代 Z，但沒有排除 X 和 Y 是同一個人的情況。當 X=Y=bo、Z=ana 時，par(ana, bo) 被使用了兩次，兩個條件都滿足。
這是一個經典的邏輯程式設計陷阱——缺少不等式約束。
加入 X ≠ Y 的約束。用自然語言描述：
「X 和 Y 是兄弟姊妹」的條件是：存在某人 Z 同時是 X 的親代和 Y 的親代，且 X 與 Y 不是同一個人。
用 Relka 語法：sib(X,Y) :- par(Z,X), par(Z,Y), X \= Y
語言學連結：anc 的遞迴定義是遞迴規則的典範——它對應語言學中的傳遞性閉包（transitive closure），與 Chomsky 層級中 CFG 的遞迴產生規則殊途同歸。而 sib 的 bug 則呼應了語意學中排除自指的問題——就像自然語言中「兄弟」一詞隱含「不是自己」的預設（presupposition），但形式化時若不明示，邏輯系統不會自動補上。
輸入 Relka 查詢（如 dad(bo, di)），引擎會顯示推導過程。