non過渡在非確定型有窮自動機中如何工作？

Question

我對自動機的語言實現感到困惑。如果有一個「過渡」，自動機會直接進入下一個狀態嗎？假設我有一個自動機，它由三個狀態a,b和c（其中a爲初始狀態，c爲接受狀態）組成，並帶有字母{0,1}。以下工作如何？

a----ɛ--->(b----0---->a) 
      (b----1---->c) 

是否接受字符串「1」？如果我們有

a---1--->b----ɛ--->c 

？字符串「1」會被接受嗎？

Answer 1

如果存在ɛ-轉換，自動機會直接進入下一個狀態嗎？

粗略地說，是的。 ɛ-轉換（在non-deterministic finite automaton或簡稱NFA中）是與任何符號消耗無關的轉換（在本例中爲0或1）。一旦理解了這一點，就很容易（在這種情況下）推導出與您的NFA等效的deterministic finite automata（或簡稱爲DFA），並識別後者描述的語言。

假設我有一個自動機[...]是否接受字符串「1」？

是。這是你的第一個NFA的一個更好的圖（乳膠curtesy和tikz）：

一個等價的DFA是：

一旦你的是，它很容易看到該NFA接受的語言是一組字符串

• 以0或更多開始0's，
• 只以一個1結尾。

字符串「1」，因爲它與零0開始，以一個1結束，確實接受。

如果我們有[...]怎麼辦？字符串「1」會被接受嗎？

是。這裏是你的第二個NFA的一個更好的圖：

一個等價的DFA是：

​​

事實上，它很容易地看到，「1」是唯一可接受的字符串， 這裏。