找出給定有限自動機的正則表示式。

問題

為給定的有限自動機構造一個正則表示式。

解決方案

步驟 1 - 讓我們寫下方程式。

q1=q1a+ ε

q1 是起始狀態，ε 將作為輸入 a 新增，該輸入 a 來自 q1 到 q1。

因此，我們寫

狀態=輸入的源狀態 * 輸入到它的狀態

步驟 2 - 同樣地，

q2=q1b+q2b

q3=q2a

步驟 3 - 讓我們首先簡化 q1。

q1=q1a+ ε

我們可以如下重寫它：

q1= ε +q1a

這類似於 R=Q+RP，其解決方案如下：

R=QP*

步驟 4 - 假設 R=q1，Q= ε，P=a

我們得到 q1 = ε.a*，因為 ε.R=R

q1=a*

步驟 5 - 將 q1 的值代入 q2 中，我們得到：

q2= q1a+q2b

=a*b+q2b

步驟 6 - 我們將此方程與 R=Q+RP 進行比較

假設 R=q2，Q=a*b，P=b

我們得到 q2=a*b.b*，因為 RR*=R+

我們將得到 q2=a*.b+

步驟 7 - 從給定的有限自動機中，如果我們想找出正則表示式，我們通常計算最終狀態的方程。

由於在給定的有限自動機中，q2 是最終狀態，並且 q2=a*b+

Bhanu Priya

更新於： 2021年6月11日

4K+ 瀏覽量

開啟您的 職業生涯

透過完成課程獲得認證

開始學習