目錄

• 目錄
• 一些前言
• 題目說明
  • 程式主架構
  • 程式介面
• 你需要有的先備知識1——高職（應該）有教你的狀態圖＆狀態表
  • 你必須會的化簡法——直接觀察法
  • 老師可能也沒說的化簡法——分組法
• 你需要有的先備知識2——高職（應該）沒教你的c++
  • vector
  • map
  • reference
  • for(變數型態 變數名稱 : 陣列)
• 程式實作解說
  • 宣告
  • 1.處理輸入
  • 2.分組
  • 3.循環
  • 4.處理輸出
• 完整程式碼展示
• 寫給自己看的小反思

一些前言

對應高職資電類專二——數位邏輯設計的8-4章節（但補充）
此筆記主要是在記錄分組法狀態表化簡的程式實作過程紀錄，本次程式使用c++撰寫，並且內容含有大量個人書寫怪癖（意即不嘻嘻的coding style，之後優化會修TT）orz。

是個挺適合放上學習歷程的小專題！
整體而言，我只花了一天多的時間完成專題報告＆程式撰寫。

不過我記得網路上搜尋的到的資料非常少（沒試過英文搜尋），所以這個程式 100% 是我自己寫的，如果有bug的話可以跟我說一下:D
然後優化有點爆掉了我很抱歉，請鞭小力點;-;

題目說明

利用分組法刪除等價項目，化簡狀態表↓

1. 根據 input 的輸出狀態分組
2. 根據同 group 的各狀態之次態是否在同組
   →同組：留著 / 不同：拆組（次態在同組者分到同⼀組）
3. 重複動作2直到無法再分組
4. 合併，狀態表只留下各組排頭，同組者由排頭替代

程式主架構

程式介面

1. 米利機
   
2. 莫爾機
   

你需要有的先備知識1——高職（應該）有教你的狀態圖＆狀態表

以防萬一學校沒有多講，我帶著講義過來了（指路：科友的數位邏輯設計參考書2023版本）

循序邏輯是利用狀態來設計的，其中循序邏輯電路可以分成 ↓

1. 不具輸入也不具輸出——依靠正反器輸出判斷，舉例就是T型正反器輸入接上一級輸出的那種電路。
2. 具有輸入但不具輸出——莫爾機。
3. 具有輸入也具有輸出——米利機。

然後我用了canva畫了有點陽春的示意圖，其中輸出跟次態的括號裡為輸入值。

看到這個應該就明白我在說什麼了吧？

了解之後我們就直接來講簡化！

米利機跟莫爾機的分組法化簡基本上是一樣的（但是這兩個不等價！！）
所以後面我以米利機為主.w.

化簡目的 → 刪除冗餘的狀態，減少正反器的需求量:D
可被化簡 ↓

1. 相等——兩個狀態在輸入相同變數後，會有相同的次態（＆輸出）
2. 等效——兩個狀態在輸入相同變數後，其一次態相同，而另一個次態是彼此（＆相同輸出）

符合上述條件的兩狀態可以化簡成一個狀態。

你必須會的化簡法——直接觀察法

舉個栗子（米利機，指路台科大圖書的數位邏輯設計2025第二版）：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	F	0	1
C	B	A	0	0
D	B	C	1	0
E	F	D	0	0
F	D	B	0	1

↑ 先觀察比較直觀的輸出，輸出一樣的再一起比較，然後我們可以分成：
輸出為 0/0 的：C、E。
輸出為 0/1 的：B、F。
輸出為 1/0 的：A、D。

然後來看 0/0 這一組，發現CE沒有相等或等效，所以跳過他們，等後面消除其他狀態之後再來看。
看 0/1 這一組，發現BF也沒辦法消去，所以跳過。
看 1/0 這一組，發現AD是相等，所以我們可以把其一化簡掉，這裡拿D化簡，然後再更新一下我們的狀態表（刪除D並且以A代替D）。

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	F	0	1
C	B	A	0	0
D	B	C	1	0
E	F	D A	0	0
F	D A	B	0	1

雖然不明顯但是D被劃掉了

↓

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	F	0	1
C	B	A	0	0
E	F	A	0	0
F	A	B	0	1

再重複剛剛的檢查方式，發現BF等效，所以刪除F並以B代替F，得到：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	B	0	1
C	B	A	0	0
E	B	A	0	0

這時候我們又發現，CE相等！最後得到：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	B	0	1
C	B	A	0	0

再來我們來點進階的

老師可能也沒說的化簡法——分組法

是這樣的，因為我聽過兩種分組法但大同小異，所以這裡只說我拿來實現程式化的分組法.w.

一樣的例題：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	F	0	1
C	B	A	0	0
D	B	C	1	0
E	F	D	0	0
F	D	B	0	1

首先我們一樣把輸出一樣的分在同一組。
輸出為 0/0 的：C、E。
輸出為 0/1 的：B、F。
輸出為 1/0 的：A、D。

組別 1	組別 2	組別 3
CE	BF	AD

對比一下第一組，C的次態(0/1)為B跟A，而E的次態(0/1)為F跟D。
發現BF都在組別 2，然後AD都在組別 3，所以組別 1 不需要再拆分開來了。

檢查剩下兩個組別會發現，都已經不需要再拆分了，所以我們可以直接化簡到剩下 3 個狀態（組別數量，各組只留一個狀態），可以得到：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	B	C	1	0
B	A	B	0	1
C	B	A	0	0

這例子有點太快了，所以我們再來一題:D

（指路：這是我老師講義的例題，所以我不確定是哪裡出的了。）

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	C	F	0	0
B	E	F	0	1
C	B	C	0	0
D	C	F	0	1
E	D	E	0	0
F	A	E	0	0

然後依照輸出分組 ↓

組別 1	組別 2
ACEF	BD

來看組別 1 ，
A的次態組別分別屬於組別 1 跟組別 1，
C的次態組別分別屬於組別 2 跟組別 1，
E的次態組別分別屬於組別 2 跟組別 1，
F的次態組別分別屬於組別 1 跟組別 1。

組別 2 ，
B的次態組別分別屬於組別 1 跟組別 1，
D的次態組別分別屬於組別 1 跟組別 1。

發現組別 1 的次態並沒有都在同一組，所以仍須被拆分！而拆分的方法則是次態在一組的拆分到同一組去（當然輸出還是要相同，所以直接在原組別內拆分即可）：

組別 1	組別 2	組別 3
AF	CE	BD

第二次檢查，來看組別 1 ，
A的次態組別分別屬於組別 2 跟組別 1，
F的次態組別分別屬於組別 1 跟組別 2。

組別 2 ，
C的次態組別分別屬於組別 3 跟組別 2，
E的次態組別分別屬於組別 3 跟組別 2。

組別 3 ，
B的次態組別分別屬於組別 2 跟組別 1，
D的次態組別分別屬於組別 2 跟組別 1。

然後發現組別 1 仍需被拆分：

組別 1	組別 2	組別 3	組別 4
A	F	CE	BD

第三次檢查，來看組別 1 ，
A的次態組別分別屬於組別 3 跟組別 2，

組別 2 ，
F的次態組別分別屬於組別 1 跟組別 3，

組別 3 ，
C的次態組別分別屬於組別 4 跟組別 3，
E的次態組別分別屬於組別 4 跟組別 3。

組別 4 ，
B的次態組別分別屬於組別 3 跟組別 2，
D的次態組別分別屬於組別 3 跟組別 2。

！！化簡完成，不必再繼續拆分，所以可以得到：

狀態名稱	次態(0)	次態(1)	輸出(0)	輸出(1)
A	C	F	0	0
F	A	C	0	0
C	B	C	0	0
B	C	F	0	1

我的程式運行結果：

題外話，我後來翻了維基百科，分組法大概就是這個了 ↓

我笨，看不懂:D

維基百科——確定有限狀態自動機最小化

你需要有的先備知識2——高職（應該）沒教你的c++

不用以防萬一了，因為這應該真沒學過了吧？

！預設你的程式已經有 struct 跟 class 的基礎了！
所以接下來你只要再學會這些就可以啦:D ↓

1. vector
2. map
3. reference
4. for(變數型態 變數名稱 : 陣列)

會的人可以直接跳到程式實作區域了！

vector

動態陣列，這裡不深講理論，請想像成很好用的陣列>w

動態陣列的大小是會隨著元素的多寡增加的，所以在新增元素的時候我們不能直接使用我們一般熟悉的 array[i] 輸入，而是要使用 array.push_back(元素)。
當然如果一開始直接使用 resize 的話是可以直接 array[i] 存取。

宣告方式為：

vector<變數型態> array;

二維陣列宣告則是將一維陣列當成變數型態：

vector<vector<變數型態>> array;

對二維陣列不熟悉的話，可以試著用上面的方法記！
對於像我這種空間感極差的人來說，會比較直觀一點，在學指標取陣列值的時候也會比較簡單。

然後我只會用到上面的知識點所以，想再深入探討的可以看看這裡。

map

map 我是無師自通的，所以原理我懂的不多，一樣不說太多。
map 直接翻譯就是地圖，那麼我們就用地圖的概念來舉例。
想像今天你在 google map 上輸入經緯度，那麼搜尋結果不就會出現你想要尋找的地點嗎？在這裡我們就可以把經緯度當成 key 值，而搜尋結果就是他的 value 值。

像這樣 ↓

map[{25°02'02.4"N, 121°33'52.9"E}] = "台北101";
map[key] = value;

當然，map[{key1, key2}] 的寫法請搭配 pair 使用 :P

宣告方式：

map<變數型態(key), 變數型態(value)> mp;

然後我後面有用到一個感覺很不健康的寫法（直覺告訴我的）↓

雖然會動，但直接對未宣告的 map 取值，有種對空指標取值的罪惡感orz

* 更：這是我家 chatgpt 說的↓

寫法	安全性	是否會插入新元素
map[key]	🚨 有風險	✅ 會插入
map.count(key)	✅ 安全	❌ 不插入
map.find(key)	✅ 安全	❌ 不插入

！請記得不要模仿我的寫法！

一樣，想要深入了解的可以看這裡。

reference

參照很好用，學了參照之後就可以代替部分 function 使用指標的地方。
簡單的想法就是想成幫變數取一個綽號，而宣告方式是這樣：

變數型態 a;
變數型態 &b = a;

之後的程式裡面，a跟b就是等價的了。
只要去更動到 b，那麼 a 也會跟著改變，使用 b 的時候可以不用像指標一樣前面加 '*'，直接寫 b 即可。

for(變數型態 變數名稱 : 陣列)

這個也很好玩，可以在學校拿來嚇同學。
迴圈的描述意思是指，取出陣列裡的所有元素。

舉例：

int array[3] = {0, 1, 2};
for(int a : array)
    cout << a << ' ';

然後就會輸出0 1 2 了！
是不是很方便呢:D

基本上只要不需要知道陣列裡的索引值，就可以使用了。

然後搭配上參照！

因為對輸出來說沒有影響，所以這裡用輸入舉例。
寫法會變成這樣：

int array[3];
for(int &a : array)
    cin >> a;
for(int a : array)
    cout << a << ' ';

如果不使用 &a 的宣告方式的話，那麼就會無法輸入。

相信這樣講完應該是懂了吧。

程式實作解說

完整程式碼（Github）
後面也有完整的程式。

宣告

狀態物件

struct state{
    string name;
    string next_state0, next_state1;
    int next_number[2];
    int output[2];
    int group_id = -1;
};

狀態：名字、兩個次態的名字、次態編號、輸出、組別編號。
（次態編號其實可以被優化刪減掉）

全域變數

map<string, int> state_id; // 紀錄狀態編號
map<string, int> groups_id; // 紀錄輸出對應的組別
vector<vector<int>> groups; // 全部的組別

state_id：⽤ map 紀錄狀態的編號（放入陣列後的編號），key 值為狀態的名字。
group_id：⽤ map 紀錄狀態組別的編號（在⼆維陣列中的編號），key 值則是輸出狀態。
groups：所有的組別，其中 group[i] = ⼀個組別，group[i][j] = 狀態編號。

1.處理輸入

    /* 1. 處理輸入 */

    // 建立狀態表

    vector<state> states;
    cout << "(Moore機第二個輸出寫\'0\')\n";
    cout << "請輸入(空格區分)\n" << "狀態名稱  輸出(0/1)  次態(0/1)\n";

    for(int i = 0; i < state_num; i++){
        state present_state;
        states.push_back(present_state);

        cin >> states[i].name >> states[i].output[0] >> states[i].output[1]
            >> states[i].next_state0 >> states[i].next_state1;
        state_id[states[i].name] = i;
    }

    // 記錄次態編號

    for(state &present_state : states){
        present_state.next_number[0] = state_id[present_state.next_state0];
        present_state.next_number[1] = state_id[present_state.next_state1];
    }

輸入狀態資訊，並且紀錄起自己的編號。
第二次的迴圈會更新紀錄狀態的次態編號。

* 動態陣列的大小會隨著元素（elements）量增加，所以在輸入的時候不能用一般陣列 cin >> array[i] 的寫法，必須先 push_back 元素，才可以進行存取。

也可以先 states.resize(state_num) 後直接使用（不用 push_back）。
後面有直接使用 resize 的作法（在第二步驟）。

2.分組

    /* 2. 分組 */

    groups.resize(state_num);

    // 第一次分組依靠輸出狀態來分

    int group_num = 0;
    for(state &present_state : states){
        string st_out;
        st_out += present_state.output[0] + '0';
        st_out += present_state.output[1] + '0';

        int index = groups_id[st_out];
        int stid = state_id[present_state.name];

        if(index == 0){
            groups[group_num++].push_back(stid);
            groups_id[st_out] = group_num;
            present_state.group_id = group_num;
        }else{
            groups[index - 1].push_back(stid);
            present_state.group_id = index;
        }
    }

一開始先重新設置了動態陣列的大小，為了後面方便存取。
其中一開始的大小先設定成狀態總數，因為最壞的情況為無法化簡。
紀錄輸出組別的是 groups_id （map），其中我利用 st_out 的字串來記錄該狀態的輸出值。

map 存取到的預設值為0，所以我在記錄狀態組別的時候，故意讓索引值+1，以方便記錄這個 key 值是否已存取過了。但如果之後要從 groups （二維vector）存取組別的時候，索引值需要再 -1。
除了利用 +1的索引值方式以外，也可以使用函式 groups_id.count(st_out) 紀錄我的 map 是否已經存取過該值了（同時也可以避免混亂）。

3.循環

這裡先上循環程式主架構 ↓

每一次的迴圈都會重新分一次組別，直到化簡至最簡。

宣告

        vector<vector<int>> new_group;
        new_group.resize(state_num);
        map<string, int> new_gpid;
        int new_gpnum = 0;

↑ 需要用到的變數，用來更新之後的組別狀態。因為分組的過程中，需要進行判別的是次態的所屬組別，如果一邊跑迴圈一邊更新資料狀態（組別）的話，會導致判斷錯誤。

循環裡的分組

        for(int i = 0; i < group_num; i++){ // 對每個組別取各元素
            vector<int> &group = groups[i];

            for(int &s : group){ // 取出陣列中的元素(各組的成員編號)
                state &st = states[s];
                string st_out;
                int ne0 = state_id[ st.next_state0 ];
                int ne1 = state_id[ st.next_state1 ];
                st_out += i + '0';
                st_out += states[ne0].group_id + '0';
                st_out += states[ne1].group_id + '0';

                int index = new_gpid[st_out];
                int stid = state_id[st.name];

                if(index == 0){
                    new_group[new_gpnum++].push_back(stid);
                    new_gpid[st_out] = new_gpnum;
                    // st.group_id = new_gpnum;
                }else{
                    new_group[index - 1].push_back(stid);
                    // st.group_id = index;
                }
            }

        }

↑ 進行分組的迴圈。
外迴圈：存取所有的組別，這裡不直接使用 for ( auto &group : groups) 的原因為在內迴圈中程式需要紀錄原本狀態所屬的組別，這樣才不會和其他組的成員編列入同一組中。

內迴圈：存取組內所有成員，並且再判斷成員之間是否可以再拆分出其他組別。其中，這裡的 st_out 在最一開始的時候，先 + i + '0'（+'0'只是換成數字的ASCII）^[1]，這樣的用法是避免後面分組的時候，與非團內成員分到同一組。
變數 ne0 和 ne1 為次態的編號（這裡可以直接使用 state.next_number[i]）。
後面分組的方式和第一次雷同。

* 程式註解的中的 st.group_id = …是錯誤的做法，因為提前更新狀態的組別資訊，會導致後面判斷組別時出錯。

迴圈重複判斷

        // 是否分完組別?

        if(new_gpnum == group_num)  break; // 組別數不變 == 已分組至最簡

        // 更新組別狀況

        for(int i = 0; i < new_gpnum; i++){
            vector<int> &group = new_group[i];
            for(int s : group){
                states[s].group_id = i+1;
            }
        }

        for(state &st : states){
            st.next_number[0] = new_gpid[st.next_state0];
            st.next_number[1] = new_gpid[st.next_state1];
        }
        groups = new_group;
        group_num = new_gpnum;
        groups_id = new_gpid;
    }

↑ 判斷迴圈是否繼續執行。
每一次的組別數呈嚴格遞增，當組別數不再增加則代表已化簡完畢。

如果化簡尚未結束，那麼會更新組別狀態，並且執行下一次的迴圈。

4.處理輸出

    /* 處理輸出 */

    cout << "\n化簡後: \n" << "狀態名稱  輸出(0/1)  次態(0/1)\n";

    for(int i = 0; i < group_num; i++){
        int j = groups[i][0];

        int next0 = state_id[states[j].next_state0];
        int next1 = state_id[states[j].next_state1];

        string ne0 = states[ groups[ states[next0].group_id - 1 ][0] ].name;
        string ne1 = states[ groups[ states[next1].group_id - 1 ][0] ].name;
        cout << states[j].name << "\t"
             << states[j].output[0] << " " << states[j].output[1] << "\t"
             << ne0 << " " << ne1 << "\n";
    }

↑ 處理輸出。
變數next0、next1為記錄次態編號（這裡可以使用 states[j].next_number[i]）。

在這裡存取 groups 的時候，都是取各組的第一個狀態的名字進行輸出，已達到使用各組中第一個元素來取代冗贅的狀態。

完整程式碼展示

/* Mealy
   Moore 的第二個輸出打0 */
#include <bits/stdc++.h>
using namespace std;

struct state{
    string name;
    string next_state0, next_state1;
    int next_number[2];
    int output[2];
    int group_id = -1;
};

map<string, int> state_id; // 紀錄狀態編號
map<string, int> groups_id; // 紀錄輸出對應的組別
vector<vector<int>> groups; // 全部的組別

int main()
{

    cout << "請輸入狀態數量 : ";
    int state_num; cin >> state_num;

    /* 1. 處理輸入 */

    // 建立狀態表

    vector<state> states;
    cout << "(Moore機第二個輸出寫\'0\')\n";
    cout << "請輸入(空格區分)\n" << "狀態名稱  輸出(0/1)  次態(0/1)\n";

    for(int i = 0; i < state_num; i++){
        state present_state;
        states.push_back(present_state);

        cin >> states[i].name >> states[i].output[0] >> states[i].output[1]
            >> states[i].next_state0 >> states[i].next_state1;
        state_id[states[i].name] = i;
    }

    // 記錄次態編號

    for(state &present_state : states){
        present_state.next_number[0] = state_id[present_state.next_state0];
        present_state.next_number[1] = state_id[present_state.next_state1];
    }

    /* 2. 分組 */

    groups.resize(state_num);

    // 第一次分組依靠輸出狀態來分

    int group_num = 0;
    for(state &present_state : states){
        string st_out;
        st_out += present_state.output[0] + '0';
        st_out += present_state.output[1] + '0';

        int index = groups_id[st_out];
        int stid = state_id[present_state.name];

        if(index == 0){
            groups[group_num++].push_back(stid);
            groups_id[st_out] = group_num;
            present_state.group_id = group_num;
        }else{
            groups[index - 1].push_back(stid);
            present_state.group_id = index;
        }
    }

    /* 3. 循環 */

    while(true){
        vector<vector<int>> new_group;
        new_group.resize(state_num);
        map<string, int> new_gpid;
        int new_gpnum = 0;

        for(int i = 0; i < group_num; i++){ // 對每個組別取各元素
            vector<int> &group = groups[i];

            for(int &s : group){ // 取出陣列中的元素(各組的成員編號)
                state &st = states[s];
                string st_out;
                int ne0 = state_id[ st.next_state0 ];
                int ne1 = state_id[ st.next_state1 ];
                st_out += i + '0';
                st_out += states[ne0].group_id + '0';
                st_out += states[ne1].group_id + '0';

                int index = new_gpid[st_out];
                int stid = state_id[st.name];

                if(index == 0){
                    new_group[new_gpnum++].push_back(stid);
                    new_gpid[st_out] = new_gpnum;
                    // st.group_id = new_gpnum;
                }else{
                    new_group[index - 1].push_back(stid);
                    // st.group_id = index;
                }
            }

        }

        // 是否分完組別?

        if(new_gpnum == group_num)  break; // 組別數不變 == 已分組至最簡

        // 更新組別狀況

        for(int i = 0; i < new_gpnum; i++){
            vector<int> &group = new_group[i];
            for(int s : group){
                states[s].group_id = i+1;
            }
        }

        for(state &st : states){
            st.next_number[0] = new_gpid[st.next_state0];
            st.next_number[1] = new_gpid[st.next_state1];
        }
        groups = new_group;
        group_num = new_gpnum;
        groups_id = new_gpid;
    }

    /* 4. 處理輸出 */

    cout << "\n化簡後: \n" << "狀態名稱  輸出(0/1)  次態(0/1)\n";

    for(int i = 0; i < group_num; i++){
        int j = groups[i][0];

        int next0 = state_id[states[j].next_state0];
        int next1 = state_id[states[j].next_state1];

        string ne0 = states[ groups[ states[next0].group_id - 1 ][0] ].name;
        string ne1 = states[ groups[ states[next1].group_id - 1 ][0] ].name;
        cout << states[j].name << "\t"
             << states[j].output[0] << " " << states[j].output[1] << "\t"
             << ne0 << " " << ne1 << "\n";
    }

}

寫給自己看的小反思

在整理筆記的時候發現的缺點們，以及期待新增功能 & 優化 ↓

1. 變數名稱超亂
2. 減少不必要的變數們
3. 介面優化
4. 減少個人奇怪的書寫怪癖
5. 原先其實預計輸出前有 sort 的功能，可以加的話是最好
6. 少用萬用標頭檔:D
7. 不要直接對沒宣告 key 值的 map 取值

不說了，能跑的程式就是好程式，優化什麼的交給未來上了資工的我吧:D

程式完成時間：2025 / 01 / 19
最後更新時間：2025 / 07 / 17

tag: 數位邏輯 狀態表化簡 Mealy Moore 程式專案 c++

---

1. 更新一下：+ i + '0' 那裡，如果 i >= 10 的話就無法達到轉換數字 ASCII 的效果，不過仍然可以達到區分字串的效果。書寫的時候沒發現很抱歉 ;-; ↩︎