在計算理論中，什麼是米利機？

在米利機中，輸出符號取決於當前輸入符號和機器的當前狀態。

輸出用每個輸入符號表示，每個狀態用“/”分隔。

米利機可以用6元組來描述

(Q, q0, Σ, O, δ, λ')

其中：

• Q：有限狀態集
• q0：機器的初始狀態
• Σ：有限輸入字母表
• O：輸出字母表
• δ：轉移函式，其中 Q × Σ → Q
• λ'：輸出函式，其中 Q × Σ → O

米利機的輸出長度等於輸入長度。

示例1

輸入 - 11

轉移 - δ (q0,11) => δ(q2,1) => q2

輸出 - 00（q0到q2的轉移輸出為0，q2到q2的轉移輸出也為0）

狀態轉換圖如下：

解釋

• **步驟1** - q0是起始狀態，輸入‘0’，它進入狀態q1併產生輸出‘0’；輸入‘1’，它進入狀態q2併產生輸出‘0’。
• **步驟2** - q1輸入‘0’保持在q1狀態併產生輸出‘0’；輸入‘1’進入q2狀態併產生輸出‘1’。
• **步驟3** - q2輸入‘1’保持在q2狀態併產生輸出‘0’；輸入‘0’進入狀態q1併產生輸出‘1’。

米利機的狀態表如下：

示例2

設計一個用於二進位制輸入序列{0,1}的米利機。

如果輸入具有子串101，則輸出為A。

如果輸入具有子串110，則輸出為B；否則，輸出為C。

狀態轉換圖如下：

狀態轉移表如下：

Bhanu Priya

更新於：2021年6月11日

3K+ 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習