Проблемы с машиной Тьюринга над языком

Question

У меня возникают проблемы с описанием машины Тьюринга, которая подходит для L = {a ^ mb ^ na ^ mb ^ n ∣ m, n≥0}

То, что у меня до сих пор таково:

Если мы начнем с пробела, строка будет пустой, и она должна принять, если нет, начать читать как, и я подумал, что маркировка a с X и b с Y будет в порядке

Answer 1

Стратегия высокого уровня для разработки TM для этого заключается в следующем:

1. Проверьте, смотрите ли вы строку вида a ^ 2k или b ^ 2k (включаяпустая строка). В любом из этих случаев остановите прием. В противном случае перейдите к шагу 2.
2. Вычеркните пары a, по одной из первой и третьей секций соответственно, до тех пор, пока в одной из секций не закончится a. Если один заканчивается, а другой все еще имеет a, остановите-отклоните. В противном случае перейдите к шагу 3.
3. Вычеркните пары b, по одной из второй и четвертой секций соответственно, до тех пор, пока в одной из секций не закончится b. Если один из них заканчивается, а у другого все еще есть b, остановите-отклоните. В противном случае остановите прием.