民國109年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第5題
下面的文法可以產生那一種字串(String)?
題目
下面的文法可以產生那一種字串(String)?
- (1) abba
- (2) ab0ab
- (3) aaba0abaa
- (4) aaba0aabaa。<W>::=0|a <W>a|b<W>b
官方答案
(3) aaba0abaa
解析
產生規則 <W>::=0 | a<W>a | b<W>b 表示 W 從 0 開始，每次可在左右對稱地加上相同的 a 或 b，因此所產生的字串必須是「以單一 0 為中心、左右完全對稱的回文（palindrome）」。檢視各選項：(1) abba 雖為回文但不含 0，無法由規則產生；(2) ab0ab 含 0 但左右不對稱（反轉為 ba0ba），非回文；(3) aaba0abaa 為回文且中心為 0，可由 W→aWa→a(bWb)a→a(b(aWa)b)a→a(b(a0a)b)a 推導出來；(4) aaba0aabaa 雖為回文，但去掉最外層 a 後內層 aba0aaba 不對稱，無法推導。故選 3。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。