成員問題（membership problem）

成員問題是你能對一個語言提出的最基本問題：給定一個字串 w 與一個語言 L，w 在 L 裡嗎？換句話說，這個特定字串屬於那個特定集合嗎？它是「拿名字去對賓客名單」的計算版本，而這正是每台識別機器被造出來要回答的問題。

精確陳述：固定一個語言 L，成員問題取一個輸入字串 w，當 w 在 L 中時必須答是、不在時答否。當語言由一台機器給定時，這就只是把機器跑在 w 上、看它是否接受。對有限自動機，你把 w 一個符號一個符號餵進去，檢查是否停在接受狀態；對上下文無關文法，你問 w 能否被推導出來；對圖靈機，你把它跑起來，看是否接受。成員問題正是抽象集合（語言）與具體計算行為（執行機器）之間的橋樑。

成員是貫穿課程中所有其他概念的脊柱。說一台機器識別語言 L，等同於說該機器解決 L 的成員問題。成員問題有多難，完全取決於 L 落在喬姆斯基階層的哪裡：對正規語言它快得不費吹灰之力（線性時間），對上下文無關語言它仍可有效率地判定（CYK 演算法約跑 O(n^3)），但對最一般的（遞迴可枚舉）語言，成員只能被識別、未必能被判定，因為機器可能在不屬於 L 的字串上永遠迴圈。所以成員問題正是可計算性與複雜度首次咬人的地方。