設計一個圖靈機，反轉包含 a 和 b 的字串

我們的目標是設計一個圖靈機 (TM)，以反轉包含字母表 {a,b} 中的 a 和 b 的字串。

示例

輸入 − aabbab

輸出 − babbaa

演算法

Step 1: Move to the last symbol, replace x for a or x for b and move right to convert the corresponding B to          „a‟ or „b‟ accordingly.
Step 2: Move left until the symbol left to x is reached.
Step 3: Perform step 1 and step 2 until „B‟ is reached while traversing left.
Step 4: Replace every x to B to make the cells empty since the reverse of the string is performed by the             previous steps.

圖靈機 (TM) 的轉換圖如下 −

讓我們考慮一個示例來檢查給定的輸入是否被反轉 −

輸入字串 - abb。

預期輸出 - {bba}

因此，TM 如下 −

Bhanu Priya

更新時間： 14-6-2021

4K+ 瀏覽

開啟你的 事業

完成課程，獲得認證

開始