Kleene Star的確定性有限自動機

Question

我讀到每個非確定性有限自動機（NFA）都可以轉換成確定性有限自動機（DFA）。這可以做爲克萊恩星正則表達式，說一個*？

以上是a *的NFA。

Answer 1

是的。 Kleene星形確定型有限自動機有兩種狀態。起始狀態是最終的，並且對於a有一個轉換到它自己，並且對於所有其他符號轉換到另一個狀態。另一個州對每個符號都有一個過渡。

因此，它接受空字符串（因爲起始狀態是最終）和a重複的任意數量。不是a的任何內容都會將DFA發送到另一個非終極狀態，並且從中無法逃脫。

如果將Kleene星形應用於比單個符號更復雜的正則表達式，它會變得稍微複雜一些，但它總是可以完成的：只需將正則表達式的NFA插入到顯示的圖像的紅色部分，並應用標準Powerset construction算法將NFA轉換爲DFA。我強烈建議學習這種算法;如果你理解爲什麼它的作品，你會看到爲什麼每個NFA可以轉換成DFA。

Answer 2

這僅僅是一個單一的起始狀態，這也是接受狀態。它有一個接受'a'的自我循環。