Создайте TM, который будет принимать язык L = {0i0j0k/ i <j <k}

Question

Как построить машину Тьюринга, которая будет принимать язык L = {0i0j0k/ i

Answer 1

Я понимаю, что это означает язык 0^i 0^j 0^k | i < j < k, По крайней мере, я не вижу других очевидных интерпретаций этого.

Самая короткая строка на этом языке получается i = 0, j = 1 а также k = 2"; это дает строку 000 на языке.

Также обратите внимание, что все строки с более чем тремя нулями также находятся в языке, так как мы можем взять i = 0, j = 1 а также k = n - 1 (за n >= 3).

Таким образом, наш язык равен 0^n | n >= 3, Этот язык является регулярным. Минимальный DFA для этого языка следующий:

Q    s    Q'
q0   0    q1
q1   0    q2
q2   0    q3
q3   0    q3

Вот, q3 является единственным принимающим государством и q0 это начальное состояние. Это предполагает, что входной алфавит состоит только из 0; если он состоит из чего-то большего, вам понадобится мертвое состояние и дополнительные произведения.

Перевод с DFA на TM оставлен в качестве упражнения.