構造一個FA（自動機理論）

Question

您需要爲所有長度爲奇數的字符串構造一個有限自動機，但在字母表{a，b}上包含偶數個b。

我已經這樣做了

((a+b)(a+b))*bb+bb*((a+b)(a+b)) 

，但我知道這是錯的，那麼，什麼是這個問題的答案？

Answer 1

你說你正在尋找一個自動機，但你的（錯誤的）答案是一個正則表達式。我會提供一個自動機。它使用兩個計數器mod 2;一個爲長度，一個爲b的數量。所以各州是：

q[0,0], q[0,1], q[1,0], q[1,1] 

例如， q [0,1]意味着總數是偶數（第一個零），而b的數目是奇數（一個）。所以最終狀態是q [1,0]，而q [0,0]是初始狀態。

的轉換是相當明顯的，做了櫃檯進行必要的修改：

q[0,0] reads a -> q[1,0] 
q[0,0] reads b -> q[1,1] 
q[0,1] reads a -> q[1,1] 
q[0,1] reads b -> q[1,0] 
q[1,0] reads a -> q[0,0] 
q[1,0] reads b -> q[0,1] 
q[1,1] reads a -> q[0,1] 
q[1,1] reads b -> q[0,0]