образом: последовательно зачеркивать в этом слове буквы a и b, по оче-
реди, а когда либо все буквы a, либо все буквы b иссякнут, посмотреть
на то, что осталось. На первый взгляд, этот алгоритм свободен от опи-
санных выше ограничений, однако по сути это не так. Несмотря на то,
что человек в ходе реализации этого алгоритма никакой дополнительной
бумаги не тратит, все же непонятно, сколько этой бумаги потребуется
для того, чтобы записать исходное слово, поскольку мы допускаем слова
произвольной конечной длины. Получается, что множество листов бума-
ги, необходимых для реализации этого алгоритма, опять должно быть
потенциально бесконечным.
Итак, человек может реализовать алгоритм для распознавания слов
языка {a
i
b
i
: i ∈ N}, однако для этого ему потребуется потенциально бес-
конечное количество таких ресурсов, как время и память. Вместо чело-
века это может сделать и какое-нибудь идеальное механическое устрой-
ство с бесконечной памятью; например, машина Тьюринга, которую мы
будем изучать в следующем разделе курса. Однако конечный автомат
этого сделать не может. Несмотря на то, что мы ничем не ограничиваем
время работы конечных автоматов, память каждого автомата конечна.
Конечный автомат — это, по определению, устройство с конечным чис-
лом состояний. Распознавая слово, автомат меняет свои состояния; в ходе
своей работы, прочитав некоторое количество букв слова, автомат при-
ходит в одно из состояний, однако он не может помнить, как он туда
попал. Если два разных слова приводят автомат в одно и то же состоя-
ние, то он не может отличить одно от другого. Именно в этом и кроется
причина того, что никакой конечный автомат не может распознать язык
{a
i
b
i
: i ∈ N}: для распознавания этого языка необходимо отличать друг
от друга все слова вида a
i
при различных i.
Конечно, для каждого конечного фрагмента языка {a
i
b
i
: i ∈ N}
можно придумать автомат, который будет правильно работать на этом
фрагменте. Например, можно придумать автомат, который будет пра-
вильно отвечать на вопрос о принадлежности слова этому языку, если
длина слова не превосходит 1000000, однако для слов больший длины он
будет давать ошибочные ответы. Можно добавить к автомату какое-то
количество новых состояний и он станет давать правильные ответы для
всех слов длины меньше 1000000000, но все равно для слов еще большей
длины неизбежны ошибки и, что самое важное, это будет уже другой
автомат. Единственный выход в данном случае — это автомат, который
в ходе своей работы мог бы сам добавлять себе новые состояния по мере
41