设计一个图灵机，反转包含 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+ 浏览

开启你的 事业

完成课程，获得认证

开始