Прибавление 1 к двоичному числу.txt

Программа: прибавление 1 к двоичному числу.

Алфавит: 0, 1, __ (пробел)
Исходное слово: 100111001
Начальное состояние: q0
Конечное состояние: qExit

Условие задачи: Программа должна прибавить 1 к двоичному числу по правилам двоичной арифметики. Пробелов в числе нет. Каретку можно оставить в любом месте (желательно на первой пустой ячейке после записанного слова). Изначально каретка стоит на -1 ячейке.

Программа:

q0, __ : __ > q1

// Проходимся по всему числу до конечного пробела.

q1, 0 : 0 > q1
q1, 1 : 1 > q1
q1, __ : __ < q2

// Если последняя цифра = 0, то меняем её на 1, и выходим из программы.
// Если поледняя цифра 1, то меняем её на 0 и движемся на -1 символ до тех пор, пока не встретим 0.
// Если 0 мы так и не встретили, то значит число состояло из одних единиц.
// Тогда в первую пустую ячейку слева дописываем 1, остальные разряды уже заполнены символами нуля.

q2, 0 : 1 > q3
q2, 1 : 0 < q2
q2, __ : 1 > q3

// Так как после предыдущих манипуляций мы могли оказаться в любом месте числа, идём до конечного пробела.
// После чего можно выходить из программы.

q3, 0 : 0 > q3
q3, 1 : 1 > q3
q3, __ : __ . qExit

Конечный результат выполнения программы: 100111110