Finite State Automaton Challenges

Автомат — это машина, которая отвечает на конкретный вопрос без вмешательства человека после его включения, например: Является ли a + b = c?

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

Окончательный автомат

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

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

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

Конечный государственный автомат с различными штатами

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

недетерминированный

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

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

Запустите этот автомат над «Аб» в своей голове: (1) Он начинается с «1», дважды запускает самопетлю «1», затем читает все «Аб», а также останавливается на «1», поэтому отклоните «Аб»; (2) Он начинается с «1», запускает самопетлю «1» один раз и переходит на «2», затем читает все «Б», а также останавливается на «2», поэтому примите «Аб».

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