民國105年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第50題
下面的文法可以產生那一種字串( S t r i n g ) ?
題目
下面的文法可以產生那一種字串( S t r i n g ) ?
- (1) a a b a 0 a b a a
- (2) a a b a 0 a a b a a
- (3) a b 0 a b
- (4) a b b a 。 <W >: : = 0 | a <W >a | b <W >b
官方答案
(1) a a b a 0 a b a a
解析
該文法 <W> ::= 0 | a<W>a | b<W>b 產生的字串特徵為：中心必定是 0，且左右兩側為鏡像對稱（迴文，palindrome）。選項1「aaba0abaa」：以 0 為中心，左側 aaba、右側 abaa，右側反轉即為 aaba，構成對稱，且可由 a(a(b(a0a)b)a)a 推導產生，故正確。選項2「aaba0aabaa」非對稱；選項3「ab0ab」左右不對稱；選項4「abba」不含中心 0，均無法由本規則產生。因此答案為1。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。