Noam Chomsky — 計算理論

生平概述

Noam Chomsky（諾姆·喬姆斯基，1928 年 12 月 7 日出生）是一位美國語言學家、哲學家、認知科學家和政治活動家，被認為是二十世紀最重要的思想家之一。他在語言學、認知科學、資訊理論和哲學領域都做出了深遠的貢獻。Chomsky 自 1955 年起在麻省理工學院（MIT）任教，度過了超過半個世紀的學術生涯。

語言學貢獻：轉換生成語法

Chomsky 最著名的學術貢獻是轉換生成語法（Transformational-Generative Grammar），在 1957 年發表的《句法結構》中首次系統性地提出：

核心概念

通用語法（Universal Grammar）：人類天生具有語言獲得裝置（LAD），兒童能在有限的輸入下快速學會語言。
表層結構與深層結構：語句有兩層結構——表層結構是實際形式，深層結構是語義來源，轉換規則連接兩者。
轉換規則：將深層結構轉換為表層結構的語法操作，如主動句和被動句之間的轉換。

以句子 "The cat ate the mouse" 為例：

S (句子)
├── NP (名詞片語)
│   ├── Det: "The"
│   └── N: "cat"
└── VP (動詞片語)
    ├── V: "ate"
    └── NP
        ├── Det: "the"
        └── N: "mouse"

Chomsky 階層

Chomsky 將形式語言分為四個層次，形成著名的 Chomsky 階層：

層次	名稱	產生式規則	識別自動機
Type 0	無限制文法	α → β（α ≠ ε）	圖靈機
Type 1	上下文相關文法	αAβ → αγβ	線性有界自動機
Type 2	上下文無關文法	A → γ	下推自動機
Type 3	正規文法	A → a, A → aB	有限狀態機

Type 0 可以產生任何遞迴可枚舉語言；Type 1 要求考慮上下文；Type 2 是程式語言語法定義的基礎；Type 3 對應正則表達式。

計算語言學影響

Chomsky 的形式語法理論對計算語言學和自然語言處理產生了深遠影響。上下文無關文法（CFG）成為描述自然語言語法的基本工具。形式語法理論直接影響了編譯器和解析器的設計，CYK 算法、Earley 算法等都源自於此。語法分析器生成器（如 Yacc、Bison）都基於 Chomsky 的理論設計。

哲學觀點與政治活動

Chomsky 是認知革命的先驅之一，認為語言學應該是認知科學的一部分，研究人類心智的內在機制。他主張語言能力部分是天生的（先天論），而非完全習得。自 1960 年代起，Chomsky 也成為知名的政治活動家和公共知識分子，批評美國外交政策和資本主義制度。