使用 Arden 定理構造給定有限自動機的正則表示式

將確定性有限自動機 (DFA) 轉換為正則表示式 (RE) 有兩種方法。這些方法如下：

• Arden 定理方法。
• 狀態消除方法。

讓我們詳細瞭解 Arden 定理方法。

Arden 定理

設 P 和 Q 為兩個正則表示式。

如果 P 不包含空字串，則關於 R 的以下方程，即 R = Q + RP，

其唯一解為 R = QP*

這裡，

• 有限自動機 (FA) 沒有 ε 移動。
• 它必須只有一個初始狀態 q1。
• 其狀態為 q1、q2、q3、…、qn。最終狀態可以是某個 qi，其中 i<=n。
• qi 是表示有限自動機接受的字串集的正則表示式，即使 qi 是最終狀態。

現在讓我們考慮一個問題，即如何使用 Arden 定理構造給定的有限自動機。

問題

透過應用 Arden 定理，找出給定有限自動機的正則表示式。

解決方案

讓我們看看這些方程。

q₀ = q₁ + q₂₀+ E

q₁ =q₀0

q₂ =q₀1

q₃ = q₁0 + q₂1+ q₃(0+1)

讓我們首先解決 q₀，如下所示：

q₀ = q₁ + q₂₀+ E

q₀ = q₁ + q₀10+ E

q₀ = q₀(01 +10)+ E

q₀ = E(01+10)*

q₀ = (01+10)*

·: R = Q+ RP

=> QP* 其中

R =q₀ ,Q =e, P= (01 + 10)

因此，正則表示式如下：

r = {01+10)*

由於 q0 是最終狀態，我們只對 q0 感興趣。

Bhanu Priya

更新於： 2021年6月11日

869 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

立即開始