finite-automata - 接受具有相等开始和结束长度的字符串的图灵机

Question

我需要帮助为这种语言创建单个磁带确定性图灵机

在这里我不确定如何确定 TM 将接受哪些字符串。如何让机器接受 a=c 的字符串？因为 b 部分包含来自 a 和 c 的元素。

Answer 1

也许您可以尝试调整一台接受回文的机器：您从左侧读取一个字符。如果它属于 {0,1}，则将其删除并向右移动（最后一个字符）。如果字符属于 {2,3}，则删除它并返回到左侧（第一个字符）。重复它直到你找到一个不属于“a”或“c”边的字符（如果你在左边，检查最后一个字符），剩余的字符应该属于“b”块。