Games worth discovering

Banner of Задачи, связанные с конечными автоматами

Screenshot 1 of Задачи, связанные с конечными автоматами

Screenshot 2 of Задачи, связанные с конечными автоматами

Screenshot 3 of Задачи, связанные с конечными автоматами

Screenshot 4 of Задачи, связанные с конечными автоматами

Задачи, связанные с конечными автоматами

Want

Автомат — это машина для ответа на конкретный вопрос без вмешательства человека после его включения, например: 1. Является ли a + b = c? 2. Содержит ли строка символов «а»? 3. Означает ли фраза «Может быть, мы могли бы выпить кофе» «Я влюблен в тебя»? (Я не думаю, что автомат для этого вопроса был разработан.) В этой игре мы будем играть с самой простой моделью автомата, автоматом с конечным состоянием, и использовать ее, чтобы справиться с 40 задачами. Они происходят из манипуляций со строками символов, двоичных чисел и повседневной жизни. Не волнуйтесь, если вы не знакомы с конечным автоматом, поскольку эта игра содержит руководство, позволяющее быстро начать работу. Кроме того, вы можете прочитать следующее введение и поискать в Интернете автомат с конечным состоянием. Конечный автомат состоит из нескольких состояний и правил переходов. Правило перехода описывает, когда одно состояние переходит в другое. Итак, это похоже на карту метро. Клиентами конечного автомата являются строки символов. Он решает, какие строки принимать, а какие отклонять. Например, FSA может принимать действительные электронные письма, номера телефонов и т. д. Теперь давайте углубимся в первый пример: он имеет два состояния: левое состояние «1» и правое состояние «2». «1», отмеченная зеленым цветом, означает, что автомат запускается здесь. «2», отмеченное синим цветом, означает, что автомат принимает входную строку только в том случае, если он остановится на этом месте и прочитает все символы в порядке строки. Следовательно, этот автомат должен принять «а» и отклонить любую другую строку. Вопрос: попробуйте самостоятельно спроектировать 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», поэтому отклоните «аб»; (2) Он начинается с «1», один раз запускает самоцикл «1» и переходит к «2», затем считывает все «b», а также останавливается на «2», поэтому примите «ab». Недетерминированный подход важен, потому что он позволяет FSA гадать, что позволяет нам спроектировать автомат естественным образом (поскольку мы, люди, любим гадать) и быстро. Некоторые применения конечного автомата. Изучение конечного автомата может помочь вам войти в мир информатики. Кроме того, он позволяет создавать множество приложений, таких как: Реализация NPC (неигрового персонажа). Чтобы улучшить взаимодействие с пользователем, во многих играх есть NPC, которые повторяют свою фиксированную логику. Например, продавец идет с запада на восток, затем с востока на запад и просит настоящего игрока купить что-нибудь, когда он приблизится. Логика настолько проста, что FSA может ее реализовать. Преимущество использования FSA по сравнению с общим языком программирования (таким как C и JAVA) заключается в том, что FSA более удобочитаем и требует меньше человеческих ресурсов для тестирования, изменения и обслуживания.

Additional information

Provider

Tramolly Game

Last Updated on

03/19/2024