設計一個圖靈機來求二進位制數的二進位制補碼

二進位制數的二進位制補碼可以透過兩種方法計算。

• 取反加一

• 從左到右遍歷位，找到第一個1位，然後反轉該1位之後的所有位。

示例

假設輸入為1110010

因此，執行二進位制補碼後，輸出如下：

輸出 - 0001110

關於使用圖靈機求二進位制補碼，

如果輸入如下：

則輸出如下：

解釋

步驟1 - 我們需要從最右端開始。

步驟2 - 我們將讀寫頭一直移到最右邊，跳過所有的0和1。

步驟3 - 向右移動時，當到達空格B時，向左移動一步。

步驟4 - 然後我們將讀寫頭向左移動，跳過所有的0。

步驟5 - 當它到達一個1時，我們將跳過這個1，然後向左移動一步。

步驟6 - 從現在開始，我們將所有的1變為0，所有的0變為1。

步驟7 - 我們將一直重複這個過程，直到字串的最左邊。

步驟8 - 一直移動到最左邊，我們將到達空格B，

步驟9 - 然後向右移動一步，使讀寫頭指向第一個字元，然後停止。

相應的圖靈機 (TM) 如下所示。這裡Q0是初始狀態，Q3是最終狀態。

解釋

藉助狀態'q0'，我們可以到達字串的末尾，當到達空格時，向左移動。

藉助狀態'q1'，我們可以經過所有0，並在找到第一個1後向左移動。

經過單個'1'然後向左移動。

藉助狀態'q2'，我們可以對每個數字取反並向左移動，當到達空格時，向右移動併到達最終狀態q2。

Bhanu Priya

更新於：2021年6月15日

7K+ 瀏覽量

開啟您的職業生涯

完成課程後獲得認證

開始學習