turing-machines - 图灵机的语言，{w#w | w ∈ {0,1}*}

Question

最近，我正在研究一个计算理论，并得到一个关于车床的问题。

让{w#w | w ∈ {0,1}*} 是车床的语言。例如，它将接受 01#01。

但是，如果我们有一台车床接受 {w#w | w ∈ {0,1}}。它会接受什么字符串？

标签： turing-machines

Answer 1

在那种情况下，w只能是0or 1，所以语言是有限的：

L = { 0#0, 1#1 }