Скачать Finite State Automaton Challenges на Windows, Mac

Автомат - это машина для ответа на конкретный вопрос без вмешательства человека после его включения, например,:
1. Является ли a + b = c?
2. Содержит ли строка символов "a"?
3. Означает ли "Может быть, мы могли бы выпить кофе" "я в тебя влюблен"? (Я не думаю, что был разработан автоматический ответ на этот вопрос.)

В этой игре мы поиграем с простейшей моделью автомата, конечным автоматом, и используем ее, чтобы справиться с 30 задачами. Они связаны с манипулированием символьными строками, двоичными числами и повседневной жизнью.

Не волнуйтесь, если вы не знакомы с Finite State Automaton, поскольку эта игра содержит руководство для быстрого начала работы. Кроме того, вы можете прочитать следующее введение и поискать Finite State Automaton онлайн, чтобы ознакомиться с ним.

Конечный автомат

Конечный автомат (FSA) является простейшим типом автомата. Конечный автомат состоит из нескольких состояний и правил перехода. Правило перехода описывает, когда одно состояние переходит в другое. Итак, это похоже на карту метро. Клиентами конечного автомата являются символьные строки. Он решает, какие строки принимаются, а какие отклоняются. Например, FSA может принимать действительные электронные письма, номера телефонов и т.д. Теперь давайте углубимся в первый пример:

У него есть два состояния: левое состояние "1" и правое состояние "2". "1", отмеченное зеленым цветом, означает, что автомат запускается здесь. "2", отмеченный синим цветом, означает, что автомат принимает входную строку только в том случае, если он остановится здесь и прочитает все символы в порядке следования строки. Следовательно, этот автомат должен принять "a" и отклонить любую другую строку.

Вопрос: попробуйте самостоятельно спроектировать FSA, принимающий "ab", и FSA, принимающий "a" или "b" (аббревиатура "a|b") (это две задачи в игре).

Недетерминированный
Наиболее существенная концепция FSA (и других типов автоматов) называется недетерминированной. Чтобы представить эту концепцию, приведем второй пример автомата. Он принимает все строки (состоящие только из 'a' и 'b'), заканчивающиеся на 'b':

Запустите этот автомат над буквой "b" в своей голове: (1) Он начинается с "1", запускает цикл "1", затем считывает все "b", а также останавливается на "1", поэтому отклоните "b"; (2) Он начинается с "1" и переходит к "2", затем считывает все "b", а также останавливается на "2", поэтому примите "b". Недетерминированный конечный автомат (NFA) принимает строку, если хотя бы одна трассировка заканчивается в состоянии, отмеченном синим цветом.

Запустите этот автомат над "ab" в своей голове: (1) Он начинается с "1", дважды запускает автоцикл "1", затем считывает все "ab", а также останавливается на "1", поэтому отклоните "ab"; (2) Он начинается с "1", один раз запускаем автоцикл "1" и переходим к "2", затем считываем все "b", а также останавливаемся на "2", поэтому принимаем "ab".

Недетерминированность важна, потому что она позволяет FSA угадывать, что позволяет нам проектировать автомат естественным образом (поскольку мы, люди, любим угадывать) и быстро.

Некоторые применения конечного автомата
Изучение конечного автомата может помочь вам войти в мир компьютерных наук. Кроме того, это может позволить вам создавать множество приложений, таких как:

NPC (неигровой персонаж) Реализация. Чтобы улучшить пользовательский опыт, во многих играх есть NPC, которые повторяют их фиксированную логику. Например, продавец едет с запада на восток, затем с востока на запад и просит реального игрока купить что-нибудь, когда они приблизятся. Логика настолько проста, что FSA может ее реализовать. Преимущество использования FSA вместо универсального языка программирования (такого как C и JAVA) заключается в том, что FSA более удобочитаем и требует меньше человеческих ресурсов для тестирования, модификации и обслуживания.