introduces a finite state automata simulator and a robot-based game associated
with it for active
theory of computation related courses. The simulator is implemented in Java
language and the automaton game based robot is build by the Lego NXT Robot set.
science research indicates that engineering students tend to have active and
sensing learning preferences, and engineering related educators are recognizing
the need for more active and collaborative learning pedagogy 13.
can be used as a supporting tool for active learning not only for theory of
computation, but also for several other courses such as automata theory,
discrete mathematics, computational models, programming languages, compiler
design and other related courses.
To show the
effectiveness of our integrated environment tools as a model of interactive
online collaborative learning tools, some experiments were carried out.
results of these experiments showed that using our tools not only improved the
learners’ performance but also improved their motivation to actively
participate in the learning process of the related subjects and seek more
knowledge on their own.
the way the machine controller responds to the input, the finite state machine
is classified into deterministic (DFA): if the controller can change from one
state to another (one) state, nondeterministic (NFA): if it changes from one
state to several states, and nondeterministic with empty move (E-NFA):
if (in addition to NFA) it can also change states in response to empty (no)
finite state machine A is defined as a 5-tuple A= (Q, Epslon,
q0, F), where Q is a finite set of states that represent the machine states, Epslon
is the set of possible inputs to the machine, sigma represents the
finite state machine controller, q0 Epslon Q is the initial
(starting) state of the machine, and F Epslon Q is the set of
possible final (accepting) states of the machine..
We used Lego
Mindstorm NXT set to build the robot (Figure 2) that we used in this research.
The robot that
was build up from Lego Mindstorm’s NXT We checked the movement of this
simulator in Windows XP and Windows Vista.
is a bilingual English/Japanese and easy to use which make it a suitable tool
for novice automata
Figure 3 shows the user interface of our simulator.
automata learners can easily use the simulator. First the learner selects the “Add
State” button to insert
any number of
states in the simulator editor. Then he/she can select “Connect” button to
connect the states with the
symbols. The “Select Start” and “Select Accept” buttons set the starting and
accepting states of the
“Move State” and “Remove State” buttons can move and remove states from the
button removes the current automaton and starts a new one. “Undo”, “Redo”, “Save”,
facilitate the editing process, saving and loading the automaton. The “Dialog
Simulator” button allows
the user to
input and visually simulate any input string. In the mean time it allows the
user to define the robot motion
and connect it
with automaton states, see Figure 4. The “Robot Simulator” button allows the
user to start the “guess
If there is a
miss in the input automaton, an error window appears when we select the
simulator button or the
After designing the automaton, users can start using the simulator or playing
the automata-guess game
as we will
explain in Sections 4.2 and 5 respectively. Figure 3 shows the simulator’s
interface with an inputted
Using the Simulator
initialization the simulator with the inputted automaton it is ready to use.
The user can then click on the
Simulator” button; the simulator window (Figure 4) will appear. The following
steps show a typical session
of using the
1. Input the
string that the user wants to test in the automaton.
2. Click on
the “Make File” button.
3. Select a
directory to save the Java file
must be able to execute command of LeJOS.)
Compile, Upload, and Execute a file
automaton file was created by the simulator and saved in a selected directory
as explained in the
subsection under the name MyFirstAutomaton.java. Explanation about how to
compile, upload and execute
file with LeJOS is given here.
Compiling a file
We use the
“nxjc” command to compile the Java file that was saved in the command
prompt. LeJOS uses the
Java compiler for compiling programs. However, it needs to replace the standard
Java library with
version of this – classes.jar. For this reason LeJOS provides a command called nxjc
that sets the boot
class path to
classes.jar. Its parameter are the same as those as javac.
“nxjc” command can compile one or more java files 10.
Linking, Uploading and Executing a file
programs are different from normal Java programs in that they do not support
dynamic class loading.
the classes used in the program are collected together and packaged in a binary
file with a .nxj extension.
is referred to as linking. The linked binary is then uploaded to the NXT. We
use the “nxj” command
10 to upload
the LeJOS NXJ file in the command prompt. There is a need to connect Lego
Mindstorm to a PC
when use it.
command is used to link, upload (to the robot) and run the java program that
created by the “nxjc”
> nxj -r
Executing a program in the robot
uploading the automaton program into the Lego NXT robot as explained in the
previous subsection, we can
execute the program and check the automaton behavior (with respect to the given
input) by observing the
and action. This process can be summarized in the following steps.
1. At the
beginning, the Lego robot’s display shows the inputted string as explained in
subsection 4.2 (see Figure 4).
2. Pushing any
button in the Lego robot will result in the string “start” shown in
Lego robot’s display.
3. Pushing any
button in Lego robot again the robot will start the motion according to the
inputted string and
(Please be sure to put the robot in an empty and wide place to be able to move
4. When the
robot completes its motions, the string “end” will appear in the Lego
5. At this
stage, pushing any button in the Lego robot will result in one of the strings “accepting”
or “rejecting” on
display showing whether the underlying automaton accepting or rejecting the
given input string.
any button in Lego robot will terminate the program.
Robot-based Automaton Game
This is a
guess automaton game. The purpose of this game is to motivate students to learn
automata with fun while
they are playing.
The game can be played by two or more players. Some players act as question
answerers. A player can be either a question master or an answerer but cannot
be both at the same time.
scenario of the game is as follows.
First, it is
the question master’s turn.
1. Using the
simulator editor, the question master input an automaton of his/her choice. At
this stage the automaton
is hidden from
the answerers players
question master then clicks on the “game” button in the input window.
Next, it is
the answerer’s turn after the question masters select the “game”
button, the answerers should try to guess
automaton by trying different inputs and observing the robot’s motion. The
procedure is as follows.
1. Input an
arbitrary (guessed) string to test in the automaton.
2. Click on
the “Make File” button.
3. Select the
saving the file, compile and upload the file to Lego robot.
repeat the guess trail as long as they like until success to know the inputted
automaton. Otherwise they can
click on the “answer”
button to see the inputted automaton.
The purpose was
to introduce a simulator and robot-based automaton game for novice learners of
automata theory and related topics.
their interest and they judged that the simulator and the robot game are
convenient as learning tool for automata theory.