構造帶 Epsilon 轉換的 NFA，正則表示式為 a+ba*。

正則表示式 R= a+ba* 分為 r1 和 r2

r1= a 和 r2= ba*

我們來繪製 r1 的非確定有限狀態自動機 (NFA)，如下所示 -

現在，我們從 r2 = ba * 開始

將 r2 分為 r3 和 r4，其中 r3=b 和 r4=a*

r3 的 NFA 如下 -

r4 的 NFA 如下 -

q5 透過 epsilon 轉換到 q6 和 q8，q6 透過 'a' 轉換到 q7，而 q7 透過 epsilon 轉換到 q6 和 q7。

r2= r3.r4

現在，連線 r3 和 r4，如下所示 -

q3 輸入 'b' 後進入 q4，q4 透過 epsilon 轉換到 q5，q5 透過 epsilon 轉換到 q6，q6 輸入 'a' 後進入 q7，而 q7 透過 epsilon 轉換到 q6 和 q8。

現在，組合所有表示式，即 R=r1+r2 =a+ba*，如下所示 -

上圖為給定正則表示式 a+ba* 的最終 NFA 帶轉換。

Bhanu Priya

更新日期： 12-6 月 -2021

8K+ 瀏覽

開啟你的 職業

完成課程，獲得認證

開始