Конечные автоматы: как код понимает текст по буквам

Представь турникет в метро: он либо закрыт, либо открыт, и переключается между этими положениями строго по правилам. Никаких полутонов. Оказывается, ровно так же устроена огромная часть кода, который читает текст по буквам. Эта простая идея называется конечным автоматом, и стоит её понять один раз, как ты начнёшь замечать её повсюду.

Машина с конечным числом настроений

Конечный автомат (по-английски finite state machine) — это воображаемая машинка, у которой есть несколько состояний. В каждый момент времени она находится ровно в одном из них. Получая на вход очередной символ, она по заранее заданным правилам решает, в какое состояние перейти дальше. И так символ за символом, пока текст не кончится.

Слово конечный здесь ключевое: состояний строго ограниченное количество, их можно пересчитать по пальцам. Машинка не помнит всю историю целиком, не ведёт длинных записей — она помнит только где находится прямо сейчас. Это и делает её такой быстрой и предсказуемой.

Вернёмся к турникету. У него два состояния: заперт и разблокирован. Входные сигналы — приложить карту или толкнуть створки. Приложил карту к запертому турникету — он разблокировался. Толкнул разблокированный — прошёл, и он снова заперся. Толкаешь запертый? Ничего не происходит, упираешься в металл. Вот тебе настоящий конечный автомат, в который ты входишь каждый день, даже не задумываясь.

Как это читает текст по буквам

Теперь представь, что нам нужно проверить, является ли строка целым числом — например, -417. Человек видит это мгновенно. А компьютеру нужно пройти по символам слева направо, и конечный автомат справляется с этим идеально.

Опишем правила простыми словами. У автомата будет несколько состояний:

• Начало: ждём первый символ. Если это минус — переходим в состояние «после знака». Если цифра — сразу в «читаем число».
• После знака: теперь обязана идти цифра, иначе строка испорчена.
• Читаем число: видим цифры — остаёмся здесь и читаем дальше. Видим что-то другое — это уже ошибка.

Скармливаем автомату -417. Минус — уходим в «после знака». Четвёрка — в «читаем число». Единица, семёрка — крутимся на месте. Строка кончилась, а мы остановились в «читаем число» — значит, это правильное число. А теперь дай ему -4a7: на букве a правил для перехода нет, и автомат честно говорит «такого я не понимаю». Вот так код и отличает осмысленный ввод от мусора — не по волшебству, а по табличке переходов.

Конечный автомат не пытается понять смысл целиком. Он задаёт один и тот же тупой вопрос на каждую букву: «куда мне идти отсюда?» — и из миллиона таких ответов складывается умное поведение.

Где автоматы прячутся прямо сейчас

Самое интересное, что эта идея не пылится в учебниках, а работает буквально под капотом твоих программ. Вот лишь несколько мест:

• Регулярные выражения. Когда ты пишешь шаблон для поиска текста, движок превращает его в конечный автомат и гоняет твою строку через состояния. Именно поэтому проверка идёт молниеносно.
• Проверка форм. Тот самый момент, когда сайт говорит «введите корректный email». Под этим часто скрывается автомат, читающий адрес по буквам: имя, собачка, домен, точка, зона.
• Светофоры и лифты. Красный, жёлтый, зелёный — это состояния, а смена по таймеру или кнопке — переходы. Управляющая логика тут буквально и есть конечный автомат.
• Игры. Поведение врага в видеоигре часто описывают состояниями: патрулирует, заметил игрока, атакует, убегает. Увидел тебя — перешёл из патруля в атаку.

Объединяет все эти примеры одно: задача разбивается на горстку чётких состояний и понятные правила перехода между ними. Как только ты так посмотришь на проблему, она часто становится в разы проще.

Почему это красивая идея

Конечные автоматы — один из самых ранних и самых изящных инструментов информатики. Их любят за честность: автомат нельзя застать врасплох. Для любого состояния и любого входного символа заранее известно, что произойдёт. Нет скрытых сюрпризов, нет запутанной памяти, которая копится где-то в углу.

Из-за этой простоты их легко рисовать. Состояния обычно изображают кружками, а переходы — стрелочками с подписями, какой символ их запускает. Получается понятная схема, которую можно прочитать без единой строчки кода — почти как карту метро, где станции это состояния, а поезда возят тебя по стрелкам.

И ещё одна важная мысль напоследок. У конечных автоматов есть предел: раз памяти у них только текущее состояние, они не умеют считать неограниченно. Например, проверить, что в строке скобки идеально парные на любую глубину вложенности, простой автомат не может — для этого нужны инструменты помощнее. Но именно знание границ делает идею взрослой. Ты понимаешь не только что автомат умеет, но и где проходит его честная черта. А с этого понимания, по сути, и начинается настоящая computer science.