民國112年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第28題
有一規則表示(Regular Expression)文法可識別字串狀態表如下,下列何者為其規則表示?(1 為起 始狀態,2 為結束狀態)
題目
有一規則表示(Regular Expression)文法可識別字串狀態表如下,下列何者為其規則表示?(1 為起 始狀態,2 為結束狀態)
- (1) aba*
- (2) ab*
- (3) ab*a
- (4) bab*
官方答案
(3) ab*a
解析
依狀態表推導：起始狀態1讀入 a 後進入狀態2；在狀態2可重複讀入 b 並停留在狀態2，對應 b* 的部分；最後再讀入 a 回到狀態2，而狀態2為結束狀態，字串才被接受。整體結構是開頭一個 a、中間零個或多個 b、結尾再一個 a，寫成正規式即 ab*a。若為 aba*，則允許以 ab 結尾且結尾可接任意多個 a，接受的字串集合不同；ab* 只允許單一 a 開頭、後面接 b，缺少結尾的 a；bab* 則要求以 b 開頭，與起始狀態的轉移不符。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。