狀態機，字符串集？

Question

我正在研究處理狀態機的作業任務。我瞭解他們是如何運作的，但是我不瞭解這個特定問題的一些方面。

Let L be the set of strings over {a,b} ending with the substring abba. 
a. Build a DFA that accepts L. 
b. Build an NFA with 6 transitions that accepts L. 

如何將L併入狀態機？ 我完全b部分輸了，但我覺得，一旦我理解部分A，B應該不會太困難。

Answer 1

讓我們備份了一下。按照慣例，「L」用於定義「語言」 - 在此上下文中，符合某些定義的一組（可能是無限）字符串。當與有限自動機打，你擔心什麼字符串「接受」使用機器和哪些是「拒絕」 &通常要接受一個給定的語言&所有字符串拒絕那些沒有在它（另一看問題的方法是你可以定義一種語言作爲機器接受的所有字符串的集合 - 它們是等價的）。

第一個問題是構建一個接受L的DFA的練習 - 即給定以「aaba」結尾的任何字符串，它會接受&，如果字符串不以「abba」結尾，則拒絕該字符串。你的困惑似乎來自於認爲L某種程度上是你機器的「一部分」;最好你將L的描述編碼到你的機器中。

第二個問題是問你做同樣的事情與NFA，用額外的限制，它只有6個過渡。

Answer 2

讓我試試這個：

Node 0: 
a -> node 1 <-- This means, "if the next character is a, then go to node 1" 
b -> node 0 
END -> error 
Node 1: 
a -> node 1 
b -> node 2 
END -> error 
Node 2: 
a -> node 1 
b -> node 3 
END -> error 
Node 3: 
a -> node 4 
b -> node 0 
END -> error 
Node 4: 
END -> Success! 
a -> node 1 
b -> node 0 

我認爲應該這樣做。每個節點有3個可能的箭頭，用於a，b或字符串結束（END）。作爲「abbaEND」一部分的每個輸入都會導致下一個節點並最終成功，並且每個不屬於「abbaEND」的輸入都會將您帶回適當的節點。基本上，如果它是一個a，它將它視爲另一個「abba」塊的開始，如果它是b，則它假定接下來會出現「abba」。早期的END是失敗的。這應該是你的DFA地圖。

所以，使用和b的任何字符串作爲輸入......這DFA只應結束的成功！如果字符串以「abba」結尾，並且應該以任何其他字符串結尾。