Abstract set of possible inputs to the

 

Abstract :

This paper
introduces a finite state automata simulator and a robot-based game associated
with it for active

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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.