民國105年 第2梯次 電腦軟體設計(C++)乙級 學科
第22題
下面的文法可以產生那一種字串( S t r i n g ) ?
題目
下面的文法可以產生那一種字串( S t r i n g ) ?
- (1) a b b a
- (2) a a b a 0 a b a a
- (3) a b 0 a b
- (4) a a b a 0 a a b a a 。 <W >: : = 0 | a <W >a | b <W >b
官方答案
(2) a a b a 0 a b a a
解析
此文法採遞迴定義：<W> 可為 0，也可在左右同時各加上一個相同的 a 或 b，所以產生的字串必定以 0 為中心、左右完全對稱，形式為 w0wᵀ。選項 2 中 0 的左邊是 aaba、右邊是 abaa，abaa 正好是 aaba 的反轉，因此合法。選項 1 完全沒有 0，無法由文法推導出來；選項 3 左邊 ab 的反轉是 ba，與右邊的 ab 不符；選項 4 左邊只有四個字元、右邊有五個字元，長度不相等也不合法。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。