Games worth discovering
Finite State Automaton Challenges
--Want
Automaton is a machine for answering a specific question without human intervention once it is turned on, such as:
1. Whether a + b = c?
2. Does a character string contain "a"?
3. Does a "Maybe we could grab a coffee" mean "I have a crush on you"? (I do not think the automaton for this question has been designed.)
In this game, we will play with the simplest automaton model, Finite State Automaton, and use it to cope with 40 challenges. They come from character string manipulation, binary numbers, and daily life.
Don't worry if you are unfamiliar with Finite State Automaton since this game contains a tutorial to get started quickly. Also, you can read the following introduction and search Finite State Automaton online to get familiar with it.Finite State Automaton
Finite State Automaton (FSA) is the simplest automaton type. A finite state automaton consists of several states and transition rules. A transition rule describes when a state transits to another. So, it looks like a metro map. The clients of a finite state automaton are the character strings. It decides which strings are accepted and which strings are rejected. For example, an FSA can accept valid emails, phone numbers, etc. Now, let's dive into the first example:
It has two states: the left state "1," and the right state "2". "1" marked with the green color means the automaton starts here. "2" marked with the blue color means that the automaton accepts the input string only if it stops here and read all characters in the order of the string. Consequently, this automaton is to accept "a" and reject any other string.
Question: try to design an FSA accepting "ab" and an FSA accepting "a" or "b" (abbr., "a|b") on your own (They are two challenges in the game).
Non-deterministic
The most essential concept of FSA (and other automaton types) is called Non-deterministic. To introduce this concept, here is the second example of an automaton. It accepts all strings (only consisting of 'a' and 'b') ending with 'b':
Run this automaton over "b" in your head: (1) It starts at "1", runs the self-loop of "1", then reads all of "b" as well as stops at "1", so reject "b"; (2) It starts at "1" and transits to "2", then reads all of "b" as well as stops at "2", so accept "b". A non-deterministic finite state automaton (NFA) accepts a string if at least one trace ends at a state marked with the blue color.
Run this automaton over "ab" in your head: (1) It starts at "1", runs the self-loop of "1" twice, then reads all of "ab" as well as stops at "1", so reject "ab"; (2) It starts at "1", run the self-loop of "1" once, and transits to "2", then reads all of "b" as well as stops at "2", so accept "ab."
Non-deterministic is essential because it allows the FSA to guess, which lets us design an automaton naturally (since we, human beings, like to guess) and quickly.
Some Applications of Finite State Automaton
Learning Finite State Automaton can help you enter the world of computer science. Also, it can let you build many applications, such as:
NPC (non-player character) Implementation. To improve user experience, many games have NPCs that repeat their fixed logic. For example, a salesman goes from west to east, then from east to west, and asks a real player to buy some stuff when they get close. The logic is so simple that the FSA can implement it. The benefit of using FSA rather than a generic programming language (such as C and JAVA) is that FSA is more readable and costs less human resources to be tested, modified, and maintained.
1. Whether a + b = c?
2. Does a character string contain "a"?
3. Does a "Maybe we could grab a coffee" mean "I have a crush on you"? (I do not think the automaton for this question has been designed.)
In this game, we will play with the simplest automaton model, Finite State Automaton, and use it to cope with 40 challenges. They come from character string manipulation, binary numbers, and daily life.
Don't worry if you are unfamiliar with Finite State Automaton since this game contains a tutorial to get started quickly. Also, you can read the following introduction and search Finite State Automaton online to get familiar with it.Finite State Automaton
Finite State Automaton (FSA) is the simplest automaton type. A finite state automaton consists of several states and transition rules. A transition rule describes when a state transits to another. So, it looks like a metro map. The clients of a finite state automaton are the character strings. It decides which strings are accepted and which strings are rejected. For example, an FSA can accept valid emails, phone numbers, etc. Now, let's dive into the first example:
It has two states: the left state "1," and the right state "2". "1" marked with the green color means the automaton starts here. "2" marked with the blue color means that the automaton accepts the input string only if it stops here and read all characters in the order of the string. Consequently, this automaton is to accept "a" and reject any other string.
Question: try to design an FSA accepting "ab" and an FSA accepting "a" or "b" (abbr., "a|b") on your own (They are two challenges in the game).
Non-deterministic
The most essential concept of FSA (and other automaton types) is called Non-deterministic. To introduce this concept, here is the second example of an automaton. It accepts all strings (only consisting of 'a' and 'b') ending with 'b':
Run this automaton over "b" in your head: (1) It starts at "1", runs the self-loop of "1", then reads all of "b" as well as stops at "1", so reject "b"; (2) It starts at "1" and transits to "2", then reads all of "b" as well as stops at "2", so accept "b". A non-deterministic finite state automaton (NFA) accepts a string if at least one trace ends at a state marked with the blue color.
Run this automaton over "ab" in your head: (1) It starts at "1", runs the self-loop of "1" twice, then reads all of "ab" as well as stops at "1", so reject "ab"; (2) It starts at "1", run the self-loop of "1" once, and transits to "2", then reads all of "b" as well as stops at "2", so accept "ab."
Non-deterministic is essential because it allows the FSA to guess, which lets us design an automaton naturally (since we, human beings, like to guess) and quickly.
Some Applications of Finite State Automaton
Learning Finite State Automaton can help you enter the world of computer science. Also, it can let you build many applications, such as:
NPC (non-player character) Implementation. To improve user experience, many games have NPCs that repeat their fixed logic. For example, a salesman goes from west to east, then from east to west, and asks a real player to buy some stuff when they get close. The logic is so simple that the FSA can implement it. The benefit of using FSA rather than a generic programming language (such as C and JAVA) is that FSA is more readable and costs less human resources to be tested, modified, and maintained.
Additional information
Provider
Tramolly GameLast Updated on
03/19/2024
Game List
FAQ
When was this game updated?
Finite State Automaton Challenges is updated at 2024-03-19.
Which studio developed this game?
The provider of Finite State Automaton Challenges is Tramolly Game.
Can I play Finite State Automaton Challenges on Android/iOS?
No.
You Might Also Like
View desktop siteTapTap looks better
on the app 
