Пример 4. Определите минимально возможное число нулей на ленте после завершения работы программы.

Программа считывает символы и переходит в состояние q1, если встречает '1', и в состояние q0, если встречает '0'. В состоянии q1, если встречает '1', переходит в q1 и записывает '1'. Если встречает '0', переходит в q0 и записывает '0'. В состоянии q0, если встречает '1', переходит в q1 и записывает '0'. Если встречает '0', переходит в q1 и записывает '1'. Минимальное число нулей достигается, когда на ленте изначально больше единиц, чем нулей. В данном случае, если лента содержит 1000 нулей и 1000 единиц, и программа стремится к записи единиц, то минимальное число нулей будет 0.