
Ціна на Finite State Automaton Challenges у Steam. Найнижча ціна, яку ми бачили, — 0,49 USD.
У цій грі ми гратимемо з найпростішою моделлю автомата — скінченним автоматом, і використовуватимемо її для подолання 80 випробувань.
Машинний переклад опису
Автомат — це машина, яка відповідає на конкретне запитання без втручання людини після її увімкнення, наприклад: чи дорівнює a + b c? У цій грі ми використовуватимемо найпростішу модель автомата — скінченний автомат — для проходження 80 випробувань. Вони стосуються маніпуляцій з рядками символів, двійкових чисел та повсякденного життя. Не хвилюйтеся, якщо ви не знайомі зі скінченними автоматами; ця гра містить посібник для швидкого статку. Крім того, ви можете прочитати наступний вступ. Скінченний автомат Скінченний автомат (FSA) — це найпростіший тип автомата. Скінченний автомат складається з кількох станів та правил переходів. Правило переходу описує, коли стан переходить в інший. Тож це схоже на карту метро. Клієнтами скінченного автомата є рядки символів. Він вирішує, які рядки приймаються, а які відхиляються. Наприклад, 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», тому відхиляє «ab»; (2) Він починає в «1», один раз виконує цикл на собі для «1» і переходить до «2», потім зчитує весь «ab», а також зупиняється в «2», тому приймає «ab». Недетермінованість важлива тим, що вона дозволяє FSA вгадувати, що дозволяє нам проектувати автомат природно (оскільки ми, люди, любимо вгадувати) і швидко.