Question

Нехай Р має вигляд Q> Я, де Q і Я - непусті слова із символів 1. Трактуючи Q і Я
як записи натуральних чисел, видати як відповідь слово 1, якщо число Q більше
числа Я, і пусте слово інакше.

Answer 1

Ответ:

Символ * використовується замість символа >

В стані Q1 автомат рухається вліво, перевіряє, чи немає там символа, змінює свій стан на Q2 та замінює 1 на 0, далі змінює свій стан на Q3 та рухається в кінець слова, коли доходить до пустої клітинки, повертається та змінює свій стан на Q4 і стирає 1, змінює свій стан на Q1 та повторює усе спочатку, доки не дійде до *. Якщо символів зліва * було більше, то замінює її на 1, стирає усі інші літери, повертається до 1 та завершує програму, якщо перше слово було рівне або більше другого, то стирає усе слово та завершує програму.