化簡步驟的順序(the order of simplification steps)
整理房間要按正確順序來:先把東西全搬出來、分類,再把要留的放回去——若你在搬走家具之前就刷地板,等於白刷一次。文法清理也一樣:化簡步驟必須以特定次序執行,因為每一步都可能製造出前面步驟才剛清掉的那種垃圾。
標準順序是:(1) 移除 ε-產生式,(2) 移除單位產生式,(3) 移除無用符號,而在步驟 3 之內,先移除非生成符號,然後才移除不可達符號。理由很具體。ε-移除必須在單位移除之前,因為消除一條 ε-產生式可能製造出新的單位產生式:A -> BC 而 B 可空,會衍生出 A -> C,這是變數對變數。單位移除必須在無用符號移除之前,因為四處複製規則並刪除改名後,可能讓某些變數變成非生成或不可達。而在無用符號移除之內,先非生成、再不可達,因為刪掉一個死路變數可能使另一個原本只能透過它到達的變數變成孤兒。
遵循正確順序意味著每項清理只需一遍,且最終文法完全化簡:沒有空規則、沒有純改名規則、沒有累贅、語言相同。順序顛倒不會讓文法出錯,但可能留下殘渣,逼你回頭重做前面的步驟。這個流程是把文法轉成喬姆斯基正規形式的前半段,接著還會加上兩個塑形步驟(替換長規則中的終端符號,以及把長規則拆成二元規則)。
順序錯了會反咬你:在 S -> AB, A -> epsilon, B -> b 中,若你先移除單位,當下一個也沒有,但接著的 ε-移除會產生 S -> B,一條全新的單位產生式,你得在第二遍才清掉。先做 epsilon、再做單位、再做無用符號,就能各掃一遍清乾淨。
先 epsilon、再單位、再無用(非生成先於不可達):否則每一步都會重新製造出前一步的垃圾。
好記的口訣是 epsilon、單位、無用——照這個順序——而在「無用」之內,先生成再可達。略過順序不會改變語言,但可能讓文法沒有完全化簡。