無用符號(useless symbol)
想像一張地鐵圖,有一站沒有任何軌道能到達,另一站的軌道則永遠繞圈、從不抵達任何目的地。對旅客而言這兩站都毫無用處。文法裡的無用符號就是這樣的變數:以同樣兩種方式,它永遠無法參與從起始符號產生出真正完成的字串。
一個變數唯有同時滿足兩個條件才有用:它必須是生成的(generating,能推導出某個全由終端符號組成的字串),而且必須是可達的(reachable,起始符號能推導出含有它的句型)。任一條件不滿足的符號就是無用的。這兩種失敗各有名稱:非生成符號(non-generating symbol)永遠無法落到終端符號(它只會不斷改寫成更多變數,像 B -> CB 那樣沒完沒了),而不可達符號(unreachable symbol)本身沒問題,但起始符號永遠到不了它。無用符號以及一切提到它們的規則都可以刪除,對語言毫無影響。
移除無用符號是化簡的最後一步,而其內部順序很重要:你必須先移除非生成符號,然後才移除不可達符號。反過來做可能留下垃圾,因為刪掉一個非生成變數,可能使原本可達的變數變成不可達。回報是一個整潔的文法,其中每個變數都確實對某個推導有所貢獻,這樣更易於剖析、轉換為正規形式,也更易於推理。
S -> a | AB, A -> a, B -> bB。這裡 B 是非生成的(B -> bB -> bbB -> ... 永遠到不了只含終端符號的字串),所以 AB 永遠無法完成;刪掉 B 與規則 S -> AB 後剩下 S -> a, A -> a。此時 A 從 S 不可達(沒有任何規則提到 A),於是也被刪除,只留下 S -> a。
兩種無用的方式:到不了終端字串,或從起始符號到不了它。
若起始符號本身竟是非生成的,則語言為空集;只有在清理後完全沒有規則時,無無用符號的文法才會產生空語言。無用符號的移除不改變成員關係,只改變整潔度。