Name: Non-Deterministic Finite Automaton
Tech: HTML5, CSS3, Javascript, jQuery, Vis.js
Platform: Desktop & Tablet Devices
Available Version: Try the NDFA simulation
Game Type
The “Non-Deterministic Finite Automaton” interactive learning environment is a Puzzle, Point & Click game which attempts to abstract the complexity of finite-state machine and acts as a practice space.
This is a learning based game but should be integrated with additional resources previous to exploring it.
Description
Aa state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. Inputs determine whether a system should change its state. The change from one state to another is called a transition. A complete finite-state machine is defined by a list of its states, its initial state, and the inputs that trigger each transition. This interactive game explores one example of finite-state machine called Non-Deterministic Finite Automaton. It is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence non-uniquely determined by the string. In this case, the non-unique symbols are represented by bits of random binary strings. The interactive environment is mainly used as a practice space for students to understand and visualise the concept of finite-state machine. Students need to correctly navigate the system to verify the acceptance of binary strings.
Terminal Leanring Objectives
This interactive learning environment has the following TLO:
- Create a visual mental model of finite-state machine
- Understand the basics of NDFS (state, transitions)
- Understand how NDFS can be applied to verify binary strings
Game Design Values
- Experience: The “Non-Deterministic Finite Automaton” interactive learning environment is a Puzzle, Point & Click game which allows the players to visualise and practice the theory of finite-state machine.
- Theme: Players are in control of traversing a non-deterministic state-machine system. Systems are represented by graphs with nodes as states and direct connection between nodes representing the transitions. A random set of binary strings dictate the inputs and eventually a change of state of the system.
- Point of View: The game is presented as a 2D environment containing images, dynamic content, and UI buttons. The game graphics are minimal but essential.
- Challenge: The main challenge is to compete against the computer in correctly traversing a non-deterministic finite-state machine system. The system is represented by clickable random graphs. Players have to correctly change the state of the system according to binary strings and successively verify their acceptance. They can finally verify their computation against the computer solution.
- Decision-making: Decisions do not happen in real-time as players can take their time when making decisions.
- Skill, strategy, chance, and uncertainty: The game keeps track of players decisions and steps when traversing non-deterministic systems. Players need to combine their knowledge and correctly execute actions. There are elements of uncertainty as random systems and binary strings are generated at each run.
- Context: The simulation is run as a web application. It has been used as part of interactive formative learning material on E-learning platforms like Coursera.
- Emotions: The “Non-Deterministic Finite Automaton” is meant to generate a feeling of excitement, discovery, and visual understanding. Students can verify their knowledge by comparing their results with the computer computation of the system.
