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

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

第 4 題／共 4 題

◀ LS 4/4

4. 有限狀態機、Moore Machine、狀態設計

#LS-13-004中有限狀態機Moore Machine狀態設計

(10%) You are designing the firmware logic for a high-security electronic lock. The lock receives a stream of binary signals (0 or 1) from a keypad. You need to draw the state transition diagrams for two different versions of the security protocol. Use Moore Machine model for both versions. Specifically, use circles to represent states with labels $S_i$ where $i$ is the index starting from 0, use arrows to represent transitions, use an arrow to point to the start state, and mark the "Unlock" state as double circles. (a) The Standard "Header-Trailer" Protocol Specification
Start-up Check: When the system first turns on, it must check for a specific "Header." The very first two signals received must be a 1 followed by another 1.
Security Violation: If the first two signals are anything other than a pair of 1s, the system detects a hack. It must immediately enter a Permanent Lockout state where it ignores all future input and never unlocks.
Monitoring: Once the valid header (11) is received, the system waits. It ignores the specific pattern of the signals in the middle.
Unlocking: The door should unlock if and only if the last two signals received were a 0 followed by another 0.
Relocking: If the system receives more signals after unlocking that break the "00" ending, the door must lock again and go back to monitoring for a new "00" ending. (b) The Advanced "Strict Rhythm" Protocol Specification We request a security update to the logic designed in (a). Please modify your Finite State Machine to incorporate the following three specific changes. All other behaviors (like the "11" start-up check) remain the same.
Enforce Alternating Data: Instead of ignoring the signals between the header and the unlock command, the system must now strictly enforce an alternating "0, 1, 0, 1..." pattern.
Immediate Lockout on Error: If this alternating rhythm is broken (for example, if two 1s appear consecutively after the header), the system must immediately enter the Permanent Lockout state.
One-Time Access: The "Relock" feature is removed. Once the door unlocks (upon receiving the "00" suffix), any further input signals are considered a security violation and must trigger the Permanent Lockout state.

參考答案與解析

兩個版本都是 Moore machine：輸出跟著狀態走，只有 Unlock 狀態（畫成雙圓圈）輸出「開鎖」，其他狀態都輸出「上鎖」。起始狀態是 $S_0$ 。以下用轉移表表示狀態圖（每一列就是從該狀態畫出的兩個箭頭）。

(a) Header-Trailer

狀態	意義	輸出	讀到 0	讀到 1
$S_0$ （起始）	等待標頭的第一個 1	上鎖	$S_2$	$S_1$
$S_1$	已收到第一個 1	上鎖	$S_2$	$S_3$
$S_2$	永久鎖定	上鎖	$S_2$	$S_2$
$S_3$	監控中，最後一個訊號不是 0	上鎖	$S_4$	$S_3$
$S_4$	監控中，最後一個訊號是 0	上鎖	$S_5$	$S_3$
$S_5$ （雙圓圈）	Unlock，最後兩個訊號是 00	開鎖	$S_5$	$S_3$

前兩個訊號不是 11 就進入 $S_2$ ，之後所有輸入都留在 $S_2$ （規則 1、2）。
收到標頭後在 $S_3$ 、 $S_4$ 之間只記錄「最後一個訊號是不是 0」，中間的內容不管（規則 3）。
連續兩個 0 進入 $S_5$ 開鎖；在 $S_5$ 再收到 0，最後兩個仍是 00，維持開鎖；收到 1 就打破 00 結尾，回到 $S_3$ 重新上鎖並監控（規則 4、5）。

(b) Strict Rhythm

狀態	意義	輸出	讀到 0	讀到 1
$S_0$ （起始）	等待標頭的第一個 1	上鎖	$S_2$	$S_1$
$S_1$	已收到第一個 1	上鎖	$S_2$	$S_3$
$S_2$	永久鎖定	上鎖	$S_2$	$S_2$
$S_3$	上一個訊號是 1（標頭或資料），下一個必須是 0	上鎖	$S_4$	$S_2$
$S_4$	上一個訊號是 0，下一個是 1 則繼續交替、是 0 則構成 00	上鎖	$S_5$	$S_3$
$S_5$ （雙圓圈）	Unlock	開鎖	$S_2$	$S_2$

與 (a) 的差別：

強制交替：標頭之後必須是 $0,1,0,1,\ldots$ 。 $S_3$ 表示剛收到 1、期待 0； $S_4$ 表示剛收到 0。
違規立即鎖定：在 $S_3$ 收到 1（連續兩個 1，包含標頭 11 之後緊接著 1）直接進入 $S_2$ ，原本 (a) 的 $S_3$ 收到 1 是留在原地。
一次性開鎖：交替序列以 0 結束後再收到一個 0，由 $S_4$ 進入 $S_5$ 開鎖； $S_5$ 收到任何訊號都進入 $S_2$ ，取消 (a) 的重新上鎖。

例如 $11\,0\,1\,0\,0$ 依序經過 $S_0\to S_1\to S_3\to S_4\to S_3\to S_4\to S_5$ 開鎖； $11\,1$ 在第三個訊號就進入 $S_2$ 。

📄 成大115

← 上一題下一題 →

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

本章題號 · 1–4 / 4

1 2 3 4