民國112年 第2梯次 電腦軟體設計(C++)乙級 學科
第10題
有一規則表示(Regular Expression)文法可識別字串狀態表如下,下列何者為其規則表示?(1 為起 始狀態,2 為結束狀態)
題目
有一規則表示(Regular Expression)文法可識別字串狀態表如下,下列何者為其規則表示?(1 為起 始狀態,2 為結束狀態)
- (1) ab*a
- (2) bab*
- (3) aba*
- (4) ab*
官方答案
(1) ab*a
解析
規則表示式 ab*a 表示：先讀入一個 a，接著可出現零個或多個 b（即 b*），最後再讀入一個 a 才會到達結束狀態 2。對應狀態表的轉移，b 的部分形成自我迴圈，開頭的 a 與結尾的 a 分別是進入與離開的轉移。若寫成 ab*，讀完 b 後會停在非結束狀態，無法接受；bab* 與 aba* 的開頭字元或結尾字元與狀態表的轉移方向不符。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。