民國101年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第39題
下面的文法可以產生那一種字串( S t r i n g ) ?
題目
下面的文法可以產生那一種字串( S t r i n g ) ?
- (1) a b b a
- (2) a b 0 a b
- (3) a a b a 0 a b a a
- (4) a a b a 0 a a b a a 。 <W >: : = 0 | a <W >a | b <W >b
官方答案
(3) a a b a 0 a b a a
解析
產生規則 <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 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。