Abstract :
This paper
introduces a finite state automata simulator and a robot-based game associated
with it for active
learning in
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.
Introduction:
Learning
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.
Our approach
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.
The preliminary
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.
Finite state
automata:
Depending on
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)
input.
Formally, a
finite state machine A is defined as a 5-tuple A= (Q, Epslon,
Sigma,
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..
Robot:
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.
5.
Simulator
Our simulator
is a bilingual English/Japanese and easy to use which make it a suitable tool
for novice automata
learners.
Figure 3 shows the user interface of our simulator.
5.1.
Initialization
Novice
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
desired input
symbols. The “Select Start” and “Select Accept” buttons set the starting and
accepting states of the
automaton. The
“Move State” and “Remove State” buttons can move and remove states from the
automaton. The
“Start New”
button removes the current automaton and starts a new one. “Undo”, “Redo”, “Save”,
and “Load”
buttons can
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
automaton”
game.
If there is a
miss in the input automaton, an error window appears when we select the
simulator button or the
game button.
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
automaton
example.
5.2.
Using the Simulator
After
initialization the simulator with the inputted automaton it is ready to use.
The user can then click on the
“Dialog
Simulator” button; the simulator window (Figure 4) will appear. The following
steps show a typical session
of using the
simulator.
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
(The directory
must be able to execute command of LeJOS.)
5.3.
Compile, Upload, and Execute a file
Assume the
automaton file was created by the simulator and saved in a selected directory
as explained in the
previous
subsection under the name MyFirstAutomaton.java. Explanation about how to
compile, upload and execute
this automaton
file with LeJOS is given here.
5.3.1.
Compiling a file
We use the
“nxjc” command to compile the Java file that was saved in the command
prompt. LeJOS uses the
standard Sun
Java compiler for compiling programs. However, it needs to replace the standard
Java library with
LeJOS’s own
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.
The
“nxjc” command can compile one or more java files 10.
Usage:
> nxjc
Example:
> nxjc
MyFirstAutomaton.java
5.3.2.
Linking, Uploading and Executing a file
LeJOS NXJ
programs are different from normal Java programs in that they do not support
dynamic class loading.
Instead all
the classes used in the program are collected together and packaged in a binary
file with a .nxj extension.
This process
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.
The “nxj”
command is used to link, upload (to the robot) and run the java program that
created by the “nxjc”
command.
Usage:
> nxj
options main-class
Example:
> nxj -r
MyFirstAutomaton
5.3.3.
Executing a program in the robot
After
uploading the automaton program into the Lego NXT robot as explained in the
previous subsection, we can
start to
execute the program and check the automaton behavior (with respect to the given
input) by observing the
robot motion
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
automaton.
(Please be sure to put the robot in an empty and wide place to be able to move
freely.)
4. When the
robot completes its motions, the string “end” will appear in the Lego
robot display.
5. At this
stage, pushing any button in the Lego robot will result in one of the strings “accepting”
or “rejecting” on
the robot’s
display showing whether the underlying automaton accepting or rejecting the
given input string.
Finally, push
any button in Lego robot will terminate the program.
6.
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
masters. Other
players are
answerers. A player can be either a question master or an answerer but cannot
be both at the same time.
A typical
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
2. The
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
the inputted
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
save directory.
4. After
saving the file, compile and upload the file to Lego robot.
They can
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.
Conclusion:
The purpose was
to introduce a simulator and robot-based automaton game for novice learners of
automata theory and related topics.
They expressed
their interest and they judged that the simulator and the robot game are
convenient as learning tool for automata theory.
