成大113 計算機數學第4題｜離散數學 Ch13 有限狀態機與語言

離散數學›Ch13 有限狀態機與語言

第 1 題／共 4 題

◀ LS 1/4

1. 有限狀態機、Moore Machine、狀態轉移圖

#LS-13-001易有限狀態機Moore Machine狀態轉移圖

(13 points) Design a finite state machine $M = (S, \varphi, \sigma, \nu, \omega)$ , where $S = \{s_1, s_2, s_3, s_4\}$ , $\varphi = \{0, 1, 2\}$ , $\sigma = \{0, 1\}$ . The machine outputs 1 if the input string contains at least three 1s, otherwise it outputs 0. 下圖為題目給定的部分狀態轉移圖，請填入圖中問號（?）處應有的內容。

參考答案與解析

狀態的意義： $s_1$ 、 $s_2$ 、 $s_3$ 分別表示目前讀到 0 個、1 個、2 個 1， $s_4$ 表示已經讀到至少三個 1。邊上的標記是「輸入, 輸出」。

問號位置	應填內容
$s_1$ 的自迴圈	$0,0$ 與 $2,0$
$s_2\to s_3$	$1,0$
$s_3$ 的自迴圈	$0,0$ 與 $2,0$
$s_3\to s_4$	$1,1$
$s_4$ 的自迴圈	$0,1$ 、 $1,1$ 與 $2,1$

說明：輸入 0 或 2 不改變 1 的個數，所以在 $s_1$ 、 $s_2$ 、 $s_3$ 都留在原狀態、輸出 0（與題目給的 $s_2$ 自迴圈 $0,0$ 、 $2,0$ 相同）。讀到第三個 1 時由 $s_3$ 進入 $s_4$ ，此時輸入已含三個 1，輸出 1。之後不論輸入什麼都至少有三個 1，留在 $s_4$ 並持續輸出 1。

📄 成大113

← 上一題下一題 →

▤完整推導請見《WH 資工筆記 · 離散數學》Ch13 有限狀態機與語言

本章題號 · 1–4 / 4

1 2 3 4