有限狀態機

Question

假設我們有三種符號：a、b、c。凡是擁有相同數目的a 與b 的字串稱為甲形字串，如aabbccab、baabbacc、ccc 均為甲形字串，但是aabcca 不是甲形字串。請畫出接受所有甲形字串的有限狀態機（finite state machine）

Answer 1

簡圖繪製如下：

←A—
(OK)—A→(A1)
↑∣ ↑∣
B B B B
∣↓ ∣↓
(B1)—A→(AB)
←A—

* 每個狀態都有一個輸入是C而回到自己的迴圈。


詳細狀態轉換表：

State Input → Next_State
---------------------------
OK A → A1
OK B → B1
OK C → OK
---------------------------
A1 A → OK
A1 B → AB
A1 C → A1
---------------------------
B1 A → AB
B1 B → OK
B1 C → B1
---------------------------
AB A → B1
AB B → A1
AB C → AB
---------------------------

啟始狀態為OK，正確的狀態也是OK！