Date of Completion of the Study: March 2006
In the study of the Computer Science, there are a lot of disciplines that are complex and difficult to understand. One of those is the study of Automata Theory, which is one of the strongest foundations of Computer Science and is introduced to college students who took up computer science and other computer related courses. Since Finite Automata is a complex phenomenon, the proponent, with the blessings of his adviser, Engineer Rodrigo Abellanosa aimed to develop Finite Automata and Regular Expression Generator – A Computer Aided Instruction Tool that could be used during classroom instructions to fourth year Computer Science students at Asia College of Technology.
The research utilized a constructive and oneshot experimental method. The responses of the students were
gathered through questionnaires. Previous records of the students were taken into consideration to determine their needs. Experts were also asked to evaluate the functionality of the developed computeraided instruction tool based on standard testing procedures. Weighted mean and percentage were used to analyze and interpret the data gathered. The book consisted of more than 90 pages and the software was developed using Microsoft Visual Basic .Net, an objectoriented programming tool.
After a thorough study, through the findings of the proponent based on the statistical results, it came out that there was a need for a new tool to be introduced to students to help them in their difficulties in understanding the subject. With this, the proponent concluded that there was a need for computer aided instructional materials in classroom instructions in finite automata, and recommended the use of Finite Automata and Regular Expression Generator (FARE) as a computeraided instruction tool to be used during classroom instructions.
Chapter 1
PROBLEM AND ITS RESEARCH DESIGN
INTRODUCTION
Rationale
Today’s domination of computer technology has changed the world so rapidly and made it too small that
one can make a roundtrip in just one click of a button. Computer today is a way of living and definitely, it will be forever. With the existence of this technology, everyone has made and progressed into a successful global community.
The proponent, a college faculty teaching computer
science subjects at Asian College of Technology,
believed that, the said success is caused basically by
one aspect in computer science – the automata theory.
The theory of computation (automata theory) made a
significant contribution to this success. Because of
its importance to the study of computers, it is
introduced to every computer school. But due to its
complexity, students find the subject very confusing
and difficult to relate; even to some professors.
The complexity of Automata Theory may lead
students, specifically fourth year who are taking
Bachelor of Science in Computer Science and Bachelor of
Science in Computer Engineering to poor understanding
on the concepts of machine and language development,
specifically, if he has poor understanding on regular
expressions and finite automata. Hence, the proponent,
as an instructor of this course at Asian College of
Technology, wished to develop software that will
simplify this problem. This is creating a program
(FARE: Finite Automata and Regular Expression
Generator) to prove that every regular expression has a
equivalent finite state machine known as finite
automata. This software was intended to be used by
instructors as instructional aid. He believed that this
could give any individual a better understanding on
the said phenomenon. Furthermore, this study can
provide fourth year students and other enthusiasts the
knowledge that will make them appreciate the importance
of Automata Theory in computer science.
The theory of computation began early in the
twentieth century, before modern electronic computers
had been invented. At that time, mathematicians were
trying to find which math problems can be solved by
simple methods and which cannot. The first step was to
define what they meant by a “simple method” for solving a problem. In other words, they needed a formal model
of computation. Several different computational models
were devised by these early researchers. One of the
models is the Turing machine which stores characters on
an infinitely long tape, with one square at any given
time being scanned by a read/write head. Recursive
functions, the other model, uses functions and function
composition to operate on numbers. The lambda calculus
uses a similar approach. Still others, including Marcov
algorithms and Post systems, use grammarlike rules to
operate on strings. All of these formalisms were shown
to be equivalent in computational power, that is, any
computation that can be performed with one can be
performed with any of the others. They are also
equivalent in power to the familiar electronic
computer, if one pretends that electronic computers
have infinite memory. Indeed, it is widely believed
that all “proper” formalizations of the concept of
algorithm will be equivalent in power to Turing
machines; this is known as the ChurchTuring thesis. In
general, questions of what can be computed by various
machines are investigated in computability theory.
The theory of computation, studies the models of
general computation, along with the limits of computing
are the following:
a. which problems are unsolvable by a computer
b. which problems are solvable by a computer, but
require such an enormous long time to compute
that the solution is impractical; and
c. Can it be harder to solve a problem than to check
a given solution?
In general, questions concerning the time or space
requirements of given problems are investigated in
complexity theory.
In addition, to the general computational models,
some simpler computational models are useful for
special, restricted applications. Regular expressions,
for example, are used to specify string patterns in
UNIX and in some programming languages such as Perl.
Finite automata are used in circuit design and in some
kind of problemsolving. Contextfree grammars are used
to specify programming language syntax.
Nondeterministic pushdown automata are another
formalism equivalent to contextfree grammars.
Primitive recursive functions are a defined subclass of
the recursive functions (www.wikipedia.com).
Automata theory is the foundation of Computer
Science. It was formed by fortunate coincidences,
involving several seemingly unrelated branches of
intellectual endeavor [Cohen 1993]. The notions of
finite automata and regular expressions were originally
developed with the neuron nets and switching circuits
in mind. Recently, they have served as useful tools in
the design of lexical analyzers, the part of a compiler
that groups characters into tokens, variable names and,
keywords [Hopcroft and Ullman 1979]. Hence, the
development of programming languages and compilers were
based on a deep understanding on the theory of
automata, specifically, finite automata and regular
expressions.
The theory of Computing serves as a foundation for
search engines, through regular expressions and pattern
matching. Regular expressions, especially when
constructed with starclosure, allow multiple words to
be formed from a “set” of rules that are provided by
the user. For example, if the regular expression is
based on ∑ = {a, b} and consists of the rule a*b, then
the following words are a subset of what is accepted
and returned to the user: ab, aab, aaab, etc. (the set
of all words that start with a “a”, could contain
multiple “a’s”, and finish with a “b”. Similarly, the
same technique is used in search engines when trying to
locate particular information based on word
recognition. Instead of using an alphabet of {a, b},
∑ = {the set of capital and lowercase letters, all
numerals, and all symbols}*. In this way, users are
allowed to enter any combination of letters, numbers,
or symbols.
According to B.S Gajic in his study entitled “An
Automata Theory Approach to Solving the Dynamic Task
Allocation Problem in Distributed Computer Systems”,
both formulation framework and evaluation environment
of algorithms for distributed systems are based on
automata theory paradigms.
He said that traditionally the automata theory
course has been taught without computers. Students work
on assignments using pencil and paper with no immediate
feedback. As a result, this course can be more
difficult for some students than most of the other
computer science courses that have handson
interaction.
Mr. Gajic further explained that an automata theory
course can be taught in an interactive, handson manner
using a computer, such as conversion of NFA to DFA,
instead of using pens and papers to prove some
theorems, a computer can be used in performing such
endeavor. At Duke, they have been using the software
tool JFLAP to provide interaction and feedback in CPS
140, their automata theory course. JFLAP is a tool for
designing and running nondeterministic versions of
finite automata, pushdown automata, and Turing
machines. Recently, they have enhanced JFLAP to allow
one to study the proofs of several theorems that focus
on conversions of languages, from one form another.
What is a Regular Expression?
An expression is a number, variable, word, or group
of words that can be evaluated using operators and
functions to form a new value [Microsoft Windows Help
1995]. The operators used in an expression are of five
types, according to Canillo on her thesis
“Expresstrain: A computerbased Expression Trainer”.
These operators are the following: grouping,
arithmetic, logical, relational, and function, which
take or accept arguments as input and return exactly
one result as output. Likewise, regular expressions use
some of these operators, particularly grouping
operator, the openclose parentheses () and the (+)
sign to give an option which character is to be read.
A regular expression (RE) is a string that
describes a whole set of strings, according to certain
syntax rule. The origin of R.E lies on automata theory
and formal language theory. These fields study models
of computation and ways to classify and describe formal
languages [www.wikipedia.com]. the operations of
concatenation and closure on sets of strings define
regular expressions, and prove that the class of
languages acceptable by finite automata is describable
by regular expressions [Hopcroft and Ullman 1979].
Thus, every regular expression has an equivalent finite
automaton. Regular expressions allow multiple words to
be formed from a “set” of rules that are provided by
the user. For example, if the regular expression is
based on ∑ = {a, b} and consists of the “rule” a*b,
then the following words are a subset of what is
accepted and returned to the user: ab, aab, aaab, etc.
The set of all words that start with an “a”, could
contain multiple “a’s”, and finish with a “b”.
What is Finite Automata?
An automation is a mathematical model for finite
state machine. A finite state machine is a machine
that, given an input, jumps through a series of states
according to a transition function (can be seen as a
table) that tells the automaton which state to go next
given a current state and a current symbol. The input
is read symbol by symbol, until it is consumed
completely (think of it’s a tape with a word written on
it that is read by a reading head of the automaton; the
head moves forward over the tape, reading one symbol at
a time). Once the input is depleted, the automaton is
said to have stopped. Depending on the state in which
the automaton stops, it’s said that the automaton
accepts or not the word in the input. If it landed in a
accept state, then the automaton accepts the word. If,
in the other hand, lands on a nonaccept state, the
word is rejected. The set of all the words accepted by
an automaton is called the language accepted by the
automaton [www.encyclopedia.thefreedictionary.com].
A finite automaton (FA) is defined as a collection
of three things: 1. a finite of states, one of which
is designated as final states; 2. an alphabet of
possible input characters, from which are formed
strings, that are to be read one character at a time;
and 3. a finite
set of transitions that tell for each state and for
each character of input alphabet which state to go
next. It is a machine that works by being presented
by letter starting at the leftmost letter. Beginning at
the start state, the characters determine a sequence of
states and it ends when the last input character is
read [Cohen 1993]. Figure 1.1 shows an example finite
state machine with its corresponding finite state
transition table show in Table 1.1 in the given rule: a
language of all words that accepts any string that has
at least two b’s and ends in b.
q2
q1
q0
Figure 1.1 An example of a finite State
Transition Graph
Condition Current State a B
Q0 q0 Q0
Q1 q1 Q1
Q2 q2 Q2
Table 1.1 Corresponding Transition Table of Finite State
Transition Graph in Figure 1.1
Table 1.1 and Figure 1.1 explain how Finite Automata
works based on a given condition. Starting at state 1
(q0), if the input is a, it loops to itself; if the
input is b, the transition goes to state 2 (q1). At
state 2, if the input is a it loops to itself; if the
input is b, transition goes to state 3 (q2). At state
3, if the input is a, transition goes to state 2; if
the input is b, it loops to itself. This illustration
gives an idea o hoe each input character moves from one
state to another based on a given rule definition, in
which very important in developing good compilers.
According to G. Odor, N. Boccara and G. Szabo in their study Phase Transition Study of a OneDimensional Probabilistic SiteExchange Cellular Automation,
the effect of mixing onedimensional probabilistic
cellular automaton with totalistic rule has been
investigated by different methods. The evolution of
the system depends on to parameters, the
probability p and the degree of mixing m. The two
dimensional phase space of parameters has been explored
by stimulation. The results are compared to the
multiplepointcorrelation approximation. By increasing
the mixing, the order of the phase transition has been
found to change from second order to first order. The
tricritical point has been located and estimates are
given for the beta component. Short and longrange
mixing is compared. This project needs a very strong
foundation on the theory of computation to realize its
implementation.
The Finite Automata and Regular Expression Generator
(FARE) Components
The concept of this study was to develop software
called Finite Automata and Regular Expression Generator
A Computer Aided Instruction Tool that would help
those who are interested to study Automata Theory.
Basically this was intended to students in the fourth
year level taking up Bachelor of Science in Computer
Science. Since Automata Theory is the study that the
proponent believed to be very complex, he came up with
an idea of creating something that would facilitate
learning – that is computeraided instruction tool.
This software basically comprises the following
components: the module that accepts input characters
that will be used as the alphabet of the language, the
rule definitions, the regular expression generator, the
finite automata transition table generator, and the
string/word evaluator.
String Evaluator
input string evaluation result
F.A. Generator
R.E. Generator
Alphabet
Rule Definition
input characters
Figure 1.2 The Conceptual Architecture of FARE
Alphabet of the Language
The module accepts the inputs from users. These
inputs should be letters or numbers. For this alphabet,
words or strings are formed based on given rule
definitions, which are generated by the machine
automatically.
The Rule Definitions
This component defines the rules of the language.
The user selects from options specific rules needed to
define the language from which regular expressions and
finite automata are generated.
The Regular Expression Generator
The Regular Expression Generator is a machine that
automatically generates regular expressions. This
machine reads from inputs (the alphabet and the rule
definitions) and designs an output RE.
The notations we use to precisely capture all the
variations that a given category of token may take are
called “regular expressions” (or, less formally “
patterns”. The word “pattern” is really vague and there are lots of other notations for patterns besides
regular expressions). Regular Expressions are a
shorthand notation for set of strings. In order to even
talk about “strings” you have to first define an
alphabet, the set of characters that can appear.
1. Caret (^) is a regular expression denoting the set
containing the empty string.
2. Ay letter in the alphabet is also a regular
expression denoting a set containing a oneletter
string consisting of that letter.
3. For regular expressions r and s, r  s is a
regular expression denoting the union of r and s.
4. For regular expressions r and s, r s is a regular
expression denoting the set of strings consisting
of a member of r followed by member of s.
5. For regular expression r, r* is a regular
expression denoting the set of strings consisting
zero or more occurrences of r.
6. You can parenthesize a regular expression to
specify operator precedence (otherwise,
alternation is like plus, concatenation is like
times, and closure is like exponentiation).
However, the program does not generate regular
expressions with positive (+) exponents like a+,
since this R.E is just the same as aa*.
The Finite Automata Transition Table Generator
Finite automata transition graph is a graph that
shows the transition of any input characters based on a
given rule definition. This graph has the following
components: start state (q0), final state (qn), and the
transition of each character after being read. The
finite automata generator is a machine that
automatically creates a valid deterministic finite
automata transition table, which is very useful in
creating transition graphs.
The String Evaluator
The string evaluator component prompts the user to
input strings and evaluates those inputs if valid or
not. This process is done by parsing each input letter
and validates it based from the given alphabet and rule
definitions. The machine will display a message for the
user input is valid or not.
THE COMPILER TECHNOLOGY
The development of FARE was a result of the
proponent’s interest to help computer science students,
4th year level visualize the importance of automata
theory, since compilers are products of this.
A compiler is a program that reads a program in one
language, the source language and translates it into
another program – the target language. An important
component of compiler is the error handler that reports
errors to the user if it encounters errors in the
source program in the translation process [Aho, Sethi,
& Ullman 1986]. A compiler conceptually operates using
the following phases, namely: lexical analyzer, syntax
analyzer, semantic analyzer, intermediate code, code
optimizer, and code generator, which eventually
produces the target language out of the different
components of compiler since this study evolved in
compiler technology.
Figure 1.3 illustrates a typical decomposition of a
compiler.
Target Program
Semantic Analyzer
Intermediate Code
Code Optimizer
Code Generator
Syntax Analyzer
Symbol Table Manager
Error Handler
Lexical Analyzer
Figure 1.3 Phases of a Compiler
The lexical analyzer is the phase that reads the
characters in the source program (expressions) and
groups them into a stream of tokens in which each token
represents a logical sequence of characters. Examples
of tokens are variables, keywords, and operators. These
tokens are then grouped by the syntax analyzer into
grammatical phrases, which are used by the compiler to
synthesize outputs. A contextfree grammar (CFG) or a
parse tree may represent the grammatical phrases of the
source program.
The semantic analyzer is the phase that checks the
program for logical errors and gathers type of
information for codegeneration. This phase uses a
hierarchical structure determined by the syntax
analyzer to identify the operator ad operands of
expressions.
The intermediate code generation then follows,
which produces a program for an abstract machine. Then
this intermediate code is improved and optimized in the
code optimizer to result a fastrunning machine.
The last phase of the compiler is the code
generator that produces the target program, which is a
machine code or assembly code.
The symbol table manager that interacts with the
six phases of compiler (as shown in Figure 1.1)
contains the symbol table, which is a data structure
containing a record for each identifier, with fields
for each identifier’s attributes. This data structure
allows for the finding of records for each identifier
quickly and for the storage and retrieval of data. When
the compiler, particularly the lexical analyzer detects
an identifier in the source program or in the
expression, this identifier is stored into the table.
The error handler is used whenever the compiler
encounters errors. This is done so that any of the
phases that encounter error can deal with it.
The proponent believed that the most critical
phases of compiler are the first two phases. Hence, he
wished to develop FARE, the software that focused on
these two phases of compiler that is the lexical and
syntax analyzer. This software reads from inputs
(alphabet component) then generates some syntax rules
(rule definition component) and phases every character
of input string to check its validity based on the
rules generated.
OBJECTORIENTED PROGRAMMING APPROACH
This study uses objectoriented approach to
simplify design and implementation of complex program.
It uses use case models to present how a user interacts
with the system as well as how the functionalities of
the system relate to each other. The implementation of
the program is in a modular technique in which one
module is equivalent to one function. Aside from use
cases, this project uses standard UML notations
formalizing the different models. These models
illustrate all functional descriptions as well as
implementation details.
Since this project is implemented using Visual
Basic.Net, which is a true objectoriented language, it
uses classes and objects to show how each component
relates to each other by which inheritance is applied.
Other objectoriented programming features are also
used in implementation, such as encapsulation,
abstraction, and polymorphism.
The Use Unified Modeling Language (UML)
The UML is a fusion of the notations from different authors, such as Booch, OOSE, and others. It focuses on the description of software development artifacts – that is the design. These descriptions are then used developers (programmers) to come up with a good implementation.
UML defines nine types of diagram to represent the various modeling viewpoints. These are the following: 1. Activity diagrams representing the behavior of operation as a set of actions. 2. Use Case diagrams represent the functions of the system from a user’s viewpoint. 3. Sequence diagrams are a temporal representation of objects and their interactions. 4. Collaboration diagrams are spatial representation objects, links and interactions. 5. Class diagrams represent the static structure in terms of classes and relationships. 6. Object diagrams
represent objects and their relationships, and correspond to simplified collaboration diagrams that do not represent message broadcasts. 7. Statechart diagrams represent the behavior of classes in terms of states. 8. Component diagrams represent the physical components of an application. 9. Development diagrams represent the development of components on particular pieces of hardware.
However, the proponent did not use all UML modeling diagrams to represent his study, instead, he used only the following: use case, sequence, class, object, component, and deployment diagrams.
METHODOLOGY
Sources of Data
Information of the most common difficulties was gathered through interviews of computer science students and some instructors handling automata Theory subject. Aside from the books being used as research materials, the proponent also used the Internet as a major source of data and other related information for the development of the study.
Methods and Techniques
The study made use of Unified Modeling Language (UML) to illustrate and depict the functionality models of the program. A parse tree was also used to illustrate how a process was simulated. Lastly, the study applied the concepts of ContextFree Grammar (CGF), to reflect the structures of each design as results of modeling, which were used to serve as bases for generating program codes.
Tools
The program was implemented using Visual basic 6.0, an Objectbased Programming language. After implementation, the program was then tested to evaluate the essential requirements to be supported. Development Process
The development process employed in this study included the following phases: data gathering, analysis, design, prototyping, program implementation, documentation, and testing. An iterative approach was also
used to revisit any phase of the development process every time some significant modifications were made in enhancing the system.
The following Gantt chart shows the sequence of activities duration in months: Activities Duration in Months
 2 4 6 8 10 12 14 16 18 20
Data Gathering          
Analysis          
Design          
Prototyping          
Program Development          
Testing          
Documentation          
Figure 1.4 Gantt Chart of Activities
that may lead to any of the four bachelor’s degree courses mentioned. Following a map of Talisay City and of Cebu City, which show the location of Asian College of Technology, Bulacao Campus and Colon Campus respectively.
Scope and Delimination of the Study
This study focused on the development of software that would automatically generate a regular expression and a deterministic finite automation transition graph. These generators would base their outputs from the alphabet and the rules being defined. The software also would be capable of accepting input strings from the user and evaluates the validity of these strings based on the generated FA and RE.
However, FARE was not capable of generating other things such as nondeterministic finite automata, parse trees, contextfree grammar, Turing machine and other concepts which are not mentioned in it’s scope. The software also limited the users from inputting more than two characters for their alphabet (users should input exactly two characters.)
Furthermore, this study used Asian College of Technology as the place of research. All it’s respondents during data gathering and testing were
students (4th year) enrolled in Automata Theory subject and some instructors (handling Automata subjects) in proponent planned to finish this before the academic year of 20052006 ends. Since this study used a constructive and a one shot experimental approach, it did not employ full survey hence it only focused on the problems discussed in the statement of the problems and the difficulties that the students were having and to those who would enroll Finite Automata Subject.
Research Procedure
The research design employed in this study started with the formulation of the problem. The proponent, after formulating the problems conceptualized possible alternatives to solve such problems, which is done through interviews and questionnaires rendered to students (of automata theory course). The group of experts are instructors who are handling automata theory subject ad given the sample software and use this as instructional aid. The results were then evaluated for decisionmaking.
The data gathering from the respondents led the proponent to the conclusion that students were having difficulties in absorbing the subject, thus an instructional device should be developed.
THE PROBLEM
This study was aimed to develop a Computer Aided Instruction tool called Finite Automata and regular Expression Generator (FARE) that could enhance the complexity of Automata Theory subject, specifically regular expressions and finite automata topics. This was intended to be used by computer science who are in fourth year level and would be done at Asian College of Technology in the academic year 20052006. This software would also have a component called “the string evaluator” that would check for the validity of any input string based on the regular expression and finite automata generated. Statement of the Problem
Specifically, this sought answers to the following questions: 1. What were the problems met by the students toward Automata Theory subject? 2. What was the level of performance of the students taking automata Theory
subject: 3.1 without using the Finite Automata and Regular Expression Generator (FARE) software; and 3.2 Using Finite Automata and Regular Expression Generator (FARE) software? 3. How functional was the development Computer Aided Instruction tool as evaluated by: 4.3 researcher based on Standardized Software Testing Procedures; and 4.4 Respondents based on their level of understanding on the Regular Expressions and Finite Automata topics? 4. Based on findings of the study, what Computer Aided Instruction tool could be recommended for implementation at Asian College Technology?
Significance of the Study
Automata theory is a major phenomenon in computer science that to be understood very well by students who were at fourth year taking up Computer Science courses. The success of this project would greatly benefit the following entities:
Students.
With the implementation of this project, fourth year students could have a better grasp of the subject matter since Finite Automata and Regular Expression Generator can give them good visualization and facilitate a better understanding of regular expression and the equivalent finite automata. Administration.
This project would also benefit the Asian College of Technology Administration because this could elevate the standard of the school. The use of FARE as instructional visual aid would help the administration produce competitive graduates of computer science course. Teachers.
This project would also benefit the academe specially, to the instructors handling automata theory subject since this could be used as visual aid in classroom instructions, which would give them lesser burden in explaining a very complex subject like Finite Automata and Regular Expressions. Other Researchers.
To individuals who wanted to make further studies on finite automata and
regular expressions, this project could be of help to them. The information in this book and it’s software could be used as a start for further studies.
RESEARCH METHODOLOGY
The method used in this study were constructive and oneshoot experimental. It employed several processes in gathering data. Information were gathered through questionnaires given to students taking up computer science who were enrolled in Automata theory subject. These students were asked to try using the software to test it’s accuracy, effectiveness and usefulness. There were also students who were asked to use the software even if they were not enrolled in Automata Theory. The proponent also observed classrooms instructions to find out what should be developed to elevate the standard of teaching finite automata. For the development of software, it employed purposive sampling to students. Experts were also asked to test FARE based on standard testing procedures.
Aside from the books being used as research materials, the proponent also surfed the Internet as a major source of data and other related information for the development of the study. Figure 1.5 shows the flow of the whole development process.
Input
Conceptualization of Possible Alternatives
Problem Formulation
Detailing of Alternatives and their Implications
Evaluation of Alternatives and Selection of Course of Action
Requirements
Process
Analysis and
Program
Testing
Analysis of Results
FARE SOFTWARE
Figure 1.5 The Research Flow of the Project
Research Environment
The study was conducted at the Institute of Computer Studies of the Asian College of Technology in Cebu City, with a campus in Bulacao, Talisay City in the Second Semester, A.Y. 20042005.
Founded on September 2, 1998 as a computertraining center, Asian College of Technology was originally named Asian Computer Institute (ACI) and was located at the Mezzanine of the Arcenas Building in Colon Street. At first, ACI only offered shortterm courses. Two years later, it offered the twoyear course in associate in Computer Science prompting it to rent a building along Mabini Street, Cebu City. In 1991, due to the tremendous demand for computer education and for the school to accommodate its increasing student population, another building along Borromeo Street was rented. This building housed not only ACT’s five exceptional computer laboratories but its offices as well – the President’s office, the Records office and the Accounting office.
In 1993, one of the most significant events in the history of ACT happened – the school was able to purchase a lot in Bulacao, Talisay, Cebu. It is in this location that a fourstorey school building then housed the school library and the College of Physical Therapy, which was then offered by the school a year later. This campus became the main campus of the school and because the school has begun offering courses other than computer courses, the name of the school was changed to Asian College of Technology (ACT). This happened in early 1995, when the school decided to open its Elementary Department, then its Preschool Department and then, much later on, the High
School Department. These departments were grouped together into one division – the Integrated School Division (ACTISD).
In 1997, another big event in the school’s history happened – the construction of the sevenstorey Rodrigo A. Abellanosa building, which housed the school’s Physical Rehabilitation Center, its miniauditorium, an outstanding AudioVisual Center and the President’s Suite.
Just recently, in 2004, the school reorganized. To new academic departments were formed – the Institute of Medical Sciences (ACTIMS), which offered two medical courses: BS in Physical Therapy and BS Nursing; and the Institute of Computer Studies (ACTICS), the respondent of this study, which offered four IT courses: BS in Computer Science, BS in Information Technology, BS in Information Management, and, BS in Computer Engineering, aside from associate degree courses.
TREATMENT OF DATA
The data gathered and tabulated in this research were analyzed using descriptive statistics, particularly weighted means, frequencies and percentages. The following statistical treatment were employed: 1. Percentage. The number of students who got the specified grade ranges. This was done to determine the performance level of the students, using the formula: P = (F/N) * 100
Where: P = percentage
F = frequency
N = number of students
100 is constant
2. Weighted Mean. This statistical formula was used to find out the attitudes of the students towards the subject. This was divided into three categories: the difficulty of the subject, the negative interest of the students towards the subject, and complexity of the subject. The formula to compute for the weighted mean is:
WM=∑ WiXi
N
Where:
WM = the weighted mean
Wi = weighted point of individual responses
Xi = frequency
N = number of respondents
Scoring Criteria
Responses of respondents were based on the following criteria and categories, which are: difficulty of the subject, negative interest towards the subject, and complexity of the subject.
A. Students’ response to the given questionnaires without using Finite Automata and Regular Expression Generator.
Range CriteriaInterpretation
2.493.00 High Students did not like the subject
(H) have negative interest in
learning the subject because of
it’s complexity.
1.602.48 ModeratelyMajority of the students did not
High (MH)like the subject because there Was no FARE used as a visual aid.
Many of them are not interested to
Learn the subject because of it’s
Complexity.
1.001.59Low Very few students have interest in (L) the subject without FARE.
B. Student’s response to questionnaires using Finite Automata and Regular Expression Generator.
RangeCriteriaInterpretation
2.49 – 3.00 High Very few students were not
(H)interested of the subject because there was FARE used as visual aid.
1.60 – 2.48 Moderately Majority of the students did
High not like the subject because
(MH) there was no FARE used as
visual aid. Many of them are not interested to learn the subject due to its complexity. 1.00 – 1.59Low Students did not like the
(L) subject because there was no
FARE. They have negative interest in learning the subject because if its complexity.
C. Experts’ evaluation of Finite Automata and Regular Expression Generator – A ComputerAided Instruction Tool based on Standard Testing Procedures. The different categories are as follows: stability, portability, dependability, efficiency, usability, and maintainability.
Range CriteriaInterpretation
2.49 – 3.00Very Experts were very satisfied
Satisfactory in the result of the
(VS) software evaluation.
1.60 – 2.48 Satisfactory Experts were satisfied in
(S) the result of the software
evaluation.
1.00 – 1.59 Not Experts were not satisfied
Satisfactory in the result of the
(L) software evaluation.
Chapter II
PRESENTATION, ANALYSIS AND INTERPRETATION OF DATA
This chapter shows the different analyses and interpretations of data
gathered during requirements gathering. It is then divided into sections presenting and analyzing the problem of the study. These sections are the following: students’ problems on automata theory subject; the level of performance of students using the software; the functionalities of the software based on standard testing procedures; and the need for Finite Automata and Regular Expression Generator (FARE).
The data gathered by the proponent were taken from the respondents’ answers through questionnaires given to them, who were mostly enrolling Automata Theory subject in the first semester of academic year 20052006. Computer teachers were also used as experts to test the functionalities of the software based on standard software testing procedures.
STUDENTS’ PROBLEMS ON AUTOMATA THEORY SUBJECT
In order to assess the way Automata Theory is taught in Asian College of Technology, the researcher made a questionnaire for the students. The data gathered are then presented in table 2.1.
Instructors of Asian College off Technology do not use any visual aid in their lectures of the subject. They have to optimize their communication skills to explain a quite complicated subject with the help of whiteboard pens to illustrate something they want to impart. Students, who are slow in comprehension as shown in table 2.1, find the subject difficult because of the way the subject is taught. The table also shows that there is a need for teachers to use visual aids in teaching the subject.
Table 2.1
Nature of the Subject According the Students without Using Finite Automata and Regular Expression Generator
Student’s ResponseCategory H(3) MH(2) L(1) _X Verbal Description Difficulty of the Subject 25 11 3 2.56 H
Negative Interest Towards the Subject 20 13 6 2.35 MH Complexity of the Subject 28 8 3 2.64 H
Average 67 35 25 2.51 H
Legend: HHighMHModerately HighLLow
Range:2.46 – 3.0 High 1.6 – 2.48 Moderately High 1.0 – 1.59 Low
Table 2.1 shows how the students evaluated the subject based on three categories namely: difficulty of the subject, student’s attitudes towards the subject, and complexity of the subject. The results show that majority of the respondents find the subject very difficult, which has a weighted mean of 2.56 with a verbal description of High (H) or 64 percent of the total respondents. This led them to get uninterested in the subject, which is also reflected in the second category having weighted mean 2.35 or 51 percent. The third category also shows that it is very complex topic based on the statistical result which is 2.64 weighted mean or 71 percent. These led some students to drop the subject or result them to fail at the end of the semester. Apparently, something must be done to solve their agonizing attitude toward the subject. These explain why Finite Automata and Regular Expression Generator (FARE) should be developed to be used as computeraided instructional tool.
The proponent in his class also observed that students needed to be motivated very well for them to give some interest in the subject. As a proof, Table 2.2 shows a big difference between students attending automata theory with and without the aid of Finite Automata and Regular Expression Generator, it shows that students got very low grades as compared in the second half of the table wherein students were taught with the aid of FARE. This means that, with FARE, learning Automata Theory could not be very difficult for the students.
Table 2.2
Performance Level of Students Who Took Automata Theory Subject (A.Y. 2005 – 2006) Grades of Students in the Midterm without using Finite Automata and Regular Expression Generator Grades of Students in the Midterm Exam using Finite Automata and Regular Expression Grades(Midterm) No. Of Students Percentage(%) Grades(Midterm) No. Of Students Percentage(%) 1.0 0 0 1.0 0 0
1.1 – 1.5 3 8.824 1.1 – 1.5 6 17.648
1.6 – 2.0 3 8.824 1.6 – 2.0 9 26.471
2.1 – 2.5 3 8.824 2.1 – 2.5 8 23.529
2.6 – 3.0 11 32.352 2.6 – 3.0 8 23.529
Above 3.0 8 23.529 Failed 1 2.941
Dropped 6 17.647 Dropped 2 5.882
Total 34 100 Total 34 100
If we look at the data in Table 2.2, we could observe that figures tell that students had low enthusiasm in learning the Finite Automata if it is taught without using an instructional aid. Considering the percentage of the number of students who got lower than 2.5 and those who failed and dropped in the midterm, which totaled to close to 74 percent, the proponent believed that FARE should be used as reflected in the second half of the table. He also learned from his students and from the information he gathered through the questionnaire made, that the topics they find very difficult are Finite Automata and Regular Expressions.
The data in above table (Table 2.2) and the information through questionnaire are implications that some strategies must have to be done, and one way is by using a tool that is animated to arouse students’ interest on the subject. These reasons led to the idea of the proponent in developing FARE.
PERFORMANCE LEVEL OF STUDENTS
The data gathered also show that only few students excelled in the subject as depicted in Table 2.2. One of the reasons of their poor performance was their lack of interest in the subject as shown in Table 2.1. They were also having problems in understanding the topics discussed by their instructor because these are pure textual, that made the subject boring and uninteresting. Notes that were placed on large pieces of paper, as visual aids were not so effective because still, there was a need of much explanations and it took time for the students to grasp the idea. For example, in the given rule definition – A language of all words that begin in a and end in b in the given alphabet ∑ = (a,b), it would take a lot of
discussions before they could create the regular expression that is – R.E = a (a + b)* b. The more they got confused if they are told to create its equivalent Finite Automata Graph. These reasons inspired the proponent to create something that would help them in their struggle.
With the help of FARE, students were gaining much interest in the subject. They developed a better understanding and were more enthusiastic. Table 2.3 shows that student’s attitudes changed positively toward Automata Theory subject. This is because of the big help the software could give to them. In the example rule definition above – A language of all words that begin in a and end in b, the regular expression R.E = a (a + b)* b could be generated right away in just one click of a button. Finite Automata Transition Table could also be generated, which could give the students guide on what is the corresponding equivalent Finite Automata Graph. In addition, FARE has string evaluator, which allowed them to input sample strings to check the validity of the language.
The data shown in Table 2.3 is an implication that FARE would be a significant tool to be used in teaching the subject. It also shows the students’ attitudes towards the subject were reversed. These proved that, considering the importance of the subject in Computer Science course, this must be learned to the optimum level, and one way to achieve such goal is through the use of FARE.
Table 2.3
Student’s Responses Towards the Subject Using FARE
Student’s ResponseCategory H(3) MH(2) L(1) _X Verbal Description Difficulty of the Subject 9 4 26 1.56 MH
Negative Interest Towards the Subject 7 5 27 1.49 L Complexity of the Subject 6 5 28 1.43 L
Average 22 14 81 1.49 L
Legend: HHighMHModerately HighLLow
The date in the above table shows that with Finite Automata and Regular Expression Generator, the degree of motivation of students in learning Finite Automata had gone high. Table 2.3 shows that there was a complete
reverse in result as compared to Table 2.1. This proved that with FARE, students get interested in Automata Theory subject. As shown in Table 2.1, 67 percent of the students find Automata Theory difficult, 69 percent get more interested and 71.7 percent find Automata Theory a simple subject. This was because of the use of computeraided instructional tool called FARE.
SOFTWARE EVALUATION BASED ON STANDARD TESTING PROCEDURES
Testing is the process used in identifying the correctness, completeness and quality of the developed software. This may use several approaches, although effective testing of complex software is a process of investigation.
In order to check its functionalities, the proponent let some experts test the Finite Automata and Regular Expression Generator (FARE) software based on standard testing procedures. These experts were computer professionals. The testing process is based on the following categories, namely: Stability, Portability, Dependability, Efficiency, Usability and Maintainability. Table 2.4 shows how the experts rate the Finite Automata and Regular Expression Generator for each testing category.
Table 2.4 Testing Results According to Experts
Testing ResultCategory VS(3) S(2) NS(1) _X Verbal Description Stability 6 0 0 3 VerySatisfactory
Portability 4 1 1 2.49 VerySatisfactory
Dependability 5 1 0 2.83 VerySatisfactory
Efficiency 5 1 0 2.83 VerySatisfactory
Usability 5 1 0 2.83 VerySatisfactory
Maintainability 5 1 0 2.83 VerySatisfactory
Average    2.8 VerySatisfactory
Legend: VS – Very Satisfactory
S – Satisfactory
NS – Not Satisfactory
Risk is one of the things that must be considered when developing software. It should not cause any damage to the users. Software stability means that there must have a minimal risk on using the software. Finite Automata and Regular Expression Generator is zerorisk, as reflected in Table 2.4. Since
it is a computeraided instructional tool, it is stand alone software.
Portability refers to the capability of the software to be transported to any environment with less effort required. This means that it can run on mostly used platforms. According to experts, as shown in the table (Table 2.4), FARE is portable because it can be transported to any environment and can run on today’s widely used operating systems.
Stand alone software are dependable in nature. This means that they do not cause any physical or economic damage in the event of failure due to any cause. Since FARE is stand alone and does not store a data in a database, it is dependable. It also developed using Visual Basic .Net, which is very dependable tool for software development. Based also on the experts’ observation during testing, FARE passed on its dependability testing.
Efficiency refers to the characteristic of the software to provide correct output with less use of resources. Usability is the userfriendliness software, and maintainability is the ability of the software to evolve to meet changing requirements.
As examined by experts, Finite Automata and Regular Expression Generator has all the needed attributes and meet the required standards and has an average weighted mean of 2.89 with an equivalent verbal description that is Very Satisfactory.
THE NEED FOR FINITE AUTOMATA AND REGULAR EXPRESSION GENERATOR
The information gathered by the researcher, through the questionnaires that were answered by the students, as his respondents proved that there was a need for Finite Automata and Regular Expression Generator to be developed and be used as computer aided instruction tool in teaching automata theory subject. Table 2.3 shows that students who had tried using the software were able to develop their interest of the subject. It was because they can visualize the concepts the teacher was trying to explain. With the use of FARE, students can create finite automata (F.A) transition graphs equal to the regular expression (R.E) given, because a transition table is
automatically generated, which can give them ease in creating F.A graphs. If we compare the data gathered in Table 2.1 and Table 2.3, there was a reverse in results. This explains that FARE is an effective tool that is very useful to students. Table 2.2 also shows that students got better grades because of FARE as compared to those who were taught traditionally without using any computeraided instructional tool. With these results, the proponent believed that the implementation of Finite Automata and Regular Expression Generator would lead students of Asian College of Technology to be better graduates.
Chapter III
REQUIREMENTS ANALYSIS AND SOFTWARE DESIGN
Functional requirements refer to what the software can do, what are the inputs it can accept and what are the processes to be done to come up with the desired output. FARE has the following functionalities:
Inputs
* Alphabet
* any character of the English alphabet
* any numeric character
* Rule
* a statement that defines what word or words are acceptable to the language
* Words
* the acceptable strings of the language
Process
* The software must be able to process input characters into alphabet of the language. * It must be able to process the rules entered by the
user. * It must be able to generate regular expression (R.E) based on the given rule. * It must be able to generate finite automata (F.A) transition table based on the given rule. * It must accept input strings and evaluate their validity based on the generated R.E. Output
* Regular Expression (R.E)
* Finite Automata (F.A) Transition table
* String evaluation result (valid or not valid)
FARE DESIGN AND MODELS
Before one can develop a good software system, models must be created first. Models are representations of real things and they are significant to software development.
There are two common ways to model software. The first approach is the structured modeling which uses dataflow diagrams (DFD) to depict the different events triggered by the user. The other approach is the objectoriented modeling which uses Unified Modeling Language (UML). This approach uses different models (Use Case Models, Class Models, Object Models, etc.) to depict the different components of the software and how they interface to each other.
Since FARE was intended to be developed using Visual Basic.Net, an objectoriented programming language, it used UML in its design model.
Use Case Model
Use Case Model is representation of the functionalities of the software from user’s point of view2. It has four components, namely: the actor, which triggers the system to function; the association line, which connects the actor to the system; the use case, which depicts one scenario of system’s functionality; and the boundary line, which refers to the boundary of the system.
Figure 3.1 shows the use case model of FARE
Finite Automata and Regular Expression Generator
<<extends>> <<extends>>
<<includes>>
Process alphabet
Process Rule Definition
Evaluate Input String
Display Evaluation Result
Create Finite Automata Transition Table
T
Create Regular Expression
Figure 3.1 Use Case Model of FARE
Use Case Descriptions
Use Case Descriptions describe the way each scenario works, what are the different objects involved in each scenario, and how these objects interrelate with each other. The following are the Use Case Description of FARE: Use Case Description for Process Alphabet
Use Case Name: Process Alphabet
Purpose: To process input characters into alphabet of the language. Initiating Actor: User
Benefiting Actor: User
Precondition: User wants to input characters to be used as alphabet of the language. Post condition: Alphabet of the language is created.
Steps:
UserSystem
1. start Fare Interface
2. input two characters
3. read characters
4. create alphabet
Use Case Description for Evaluate Rule Definition
Use Case Name: Evaluate Rule Definition
Purpose: To evaluate the rule defined by the user.
Initiating Actor: User
Benefiting Actor: User
Precondition: Alphabet is created.
Post condition: Rule is defined.
Steps:
UserSystem
1. input rule definition
2. click evaluate button
3. evaluate rule
4. if rule is accepted
4.1 create R.E
4.2 create F.A
5. display R.E and F.A
Use Case Description for Create Regular Expression
Use Case Name: Create Regular Expression
Purpose: To create Regular Expression based on a given rule definition. Initiating Actor: User
Benefiting Actor: User
Precondition: Rule definition is evaluated.
Post condition: Regular Expression is created.
Steps:
UserSystem
1. parse each other
2. assign character based on the rule
3. form a regular expression
Use Case Description for Create Finite Automata Transition Table Use Case Name: Create Finite Automata Transition Table
Purpose: To create a Finite Automaton Transition Table based on a given rule definition. Initiating Actor: User
Benefiting Actor: User
Precondition: Rule definition is evaluated.
Post condition: Finite Automaton Transition Table is created. Steps:
UserSystem
1. parse each other
2. assign character based on the rule
3.form a finite automaton transition table
Use Case Description for Evaluate Input String
Use Case Name: Evaluate Input String
Purpose: To evaluate the validity of string entered by the user. Initiating Actor: User
Benefiting Actor: User
Precondition: Rule definition is evaluated.
Post condition: input string is evaluated.
Steps:
UserSystem
1. input string
2. parse characters
3. compare the string entered to the created R.E
4. display evaluation result
Use Case Description for Display Evaluation Result
Use Case Name: Display Evaluation Result
Purpose: To display the result of evaluation of any input string. Initiating Actor: User
Benefiting Actor: User
Precondition: String is compared to R.E.
Post condition: Evaluation result is displayed.
Steps:
UserSystem
1. create message window
2. if string is accepted then
2.1 display “valid” else display “not valid”
Sequence Diagram
Sequence Diagram is temporal representation of objects and their interactions. It shows the sequence of events happening in each scenario and
what objects are involved in such scenario.
:AlphabetUI
Create Alphabet
:System
input character [send message] [create alphabet]
[display] [send alphabet] [create] User
Figure 3.2 Process Alphabet:
:Rule DefinitionUI
Rule Definition
:System
input rule [send message] [create rule]
[response] [send rule] [create] User
Figure 3.3 Process Rule Definition:
:Evaluate StringUI
Evaluate String
:System
input string [send message] [evaluate string]
[display result] [send result] [evaluate] User
Figure 3.4 Evaluate Input String
REList
:CreateREUI
:System
input string [send message] [evaluate string]
[display result] [send result] [create] User
Figure 3.5 Create Regular Expression Generator
Class Diagram
In Objectoriented programming, a class is defined as a collection of the same objects. This class instantiates to create new objects. One system can contain several classes and they interact with each other which can be shown in a class diagram. Class Diagrams show the static structure of the software’s classes and their relationships.
FARE’s class diagram includes the following classes: REList, FATransitionTable, StringEvaluator, Alphabet, and TransitionTableList.
Figure 3.6 shows how these classes interact with each other.v Class:Alphabet
FirstCharSecondChar
sCreateAlphabet()
Class:StringEvaluator

showState()
Class:TransitionTable

CreateRuleDefinition
Class: FATransitionTable

ShowTransitionTable()GetTransitionCollection()
Class:REList

ShowRE()
Class:EvaluateExpression

EvalStr()showRegularExpression()showTransitionTable()TransTableCollectionCount()GetTransitionCollection()
Figure 3.6 Class Model of FARE
Object Diagram
Object is an instance of a class. It represents one realization or appearance of one of the same collection. Object diagram depicts the relationships among objects in the system at a given time. :Alphabet
FirstChar: aSecondChar: b
:String

:TransTable

:FiniteAutomata

:RegExpression

EvaluateExpression

Figure 3.7: Object Model of FARE
Interface Design
This part shows the different interfaces of the software. Its purpose is to give the users a view on how FARE works for them to have some orientation of
the software. Fare has only one main interface as shown on Figure 3.8. the different components, which would the user interacts are all placed in its main form. The proponent made this design so that users would not have hard times getting oriented with it.
//image
Figure 3.8: Main Interface of FARE
The rectangular textbox at the top center of the form serves as input box for two characters to be used as alphabet of the language. The capital S at the left most part of the textbox after the equal sign is a symbol, which implies “Alphabet of the Language.”
The large textbox at the left side of the form serves as input box for rule definition. This is where the user inputs rule of the language after the alphabet is created. The “Evaluate” button control right it is the one used in generating R.E and F.A transition table.
The textbox with the label “Regular Expression” above it is where the generated Regular Expression appears. Below the R.E textbox is the F.A transition table grid. This is where the generated F.A transition table is displayed.
At the lower most portion of the form, the string evaluator textbox is placed. This interface would accept input string from user and validate it in accordance to the generated R.E and F.A based from the rule definition. The “Evaluate” button at its right, upon clicking would automatically check the validity of the input string, a message box would pop containing the result of evaluation. Figure 4.8 and Figure 4.9 show the software functioning. //image
Figure 3.9 FARE with sample input Rule Definition with the generated RE and FA
This is how the software works. The rule must start with the phrase “a
language that accepts any string” followed by the rule description.
//image
Figure 3.10: FARE with sample input string to be validated
//image
Figure 3.11: Validation result on the input string
The proponent designed a very simple interface so that the users would not have a hard time learning how to use the software. This was done to comply the requirement of software, which is the usability requirement.
Chapter 4
SUMMARY, CONCLUSION, FINDINGS AND RECOMMENDATION
Summary
Automata Theory is a very important subject in computer science course. Students should be aware of its significance in the field that they are trying to be in. however, it should be taught properly for them to feel that this is not so complex and difficult so that they would get interested in learning.
After a long course of study, the proponent was able to tap everything and came up with this summary: Automata Theory could not be so difficult if an appropriate strategy would be applied. The development of FARE was a proof to this statement as shown in Figure 2.3 in chapter 2. The problems stated in chapter 1 could be minimized ones this software is used as a tool in teaching.
The experts, based on their evaluation on the validity of FARE proved that this could be helpful to fourth year computer science students, since it had passed through the standards stated in the standard testing procedures. Conclusion
The proponent, after a thorough study, investigation and research came up
with the conclusion that – for the students to appreciate the subject, it must be taught with some use of visual aids. These visual aids should be animated to get the interest of the students taking the subject, and the best way to have an animated tool is to develop a computer aided instruction tool.
He also concluded that students would gain interest in learning Finite Automata if something had to be done. That is using computer aided instruction tool during classroom discussions. He firmly believed that the implementation of FARE could help students think that the subject is not very complex and difficult instead, a challenge to their ability and intellect.
Lastly, he concluded that Finite Automata and Regular Expression Generator is a very effective instructional tool as reflected in Table 2.3 of Chapter 2. Nevertheless, FARE had also passed the standards required in a software as evaluated and given a very satisfactory rating by experts as shown in Table 2.4 of Chapter 2. Findings
The statistical data found in Presentation, Analysis and Interpretation of Data (Chapter 2) is more than enough for the proponent to find out how the students were performing in the previous semesters, especially in Automata Theory subject. He discovered how his students in the past semesters suffered because of poor teaching materials. He was unaware of the fact not until he conducted such study.
Furthermore, he then realized that students can be better if given the proper attention and support as what he had found out in his analysis and interpretation of the data he had gathered.
Lastly, he also realized that the use of a computer aided instruction tool could alleviate the subject, since this can give students the idea on how significant regular expressions and finite automata in developing compilers and other software. Recommendation
Considering the above conclusion and findings, the proponent strongly
recommend that Finite Automata and Regular Expression Generator should be used in Asian College of Technology as instructional aid during classroom instructions, specifically during topics wherein it is very applicable, such as conversion of Regular Expressions to Deterministic Finite Automata. He has a firm conviction that this would really change the students’ attitudes and eventually would appreciate the importance of Automat Theory in the study of computer science. Furthermore, he recommend this book to those who want to make an independent study on automata theory to be used as reference, since this had entailed some information that might be of help to their research. Lastly, he recommended this book for further study and evaluation for the enhancement of the developed software.
BIBLIOGRAPHY
Books
Ullman, Jeffrey et al. “Introduction to Automata Theory, Languages, and Computation”, AddisonWesley, Reading, Massachusettes, 1979 Daniel A. Cohen, “Introduction to Computer Theory, 2nd Edition”, John Wiley & Sons, Inc. New York, 1997. Harry R. Lewis and Christos H. Papadimitrou, “Elements of the Theory of Computation, 2nd Edition”, prentice Hall, New Jersey, 1998. Fraser and Hansen, “A Retargetable C Compiler: Design and Implementation”, Benjamin/Cummings Publishing Company, Redwood City, Ca., 1995. Fischer and Le Blanc, “Crafting a Compiler”, Benjamin/Cummings Publishing Company, Redwood City, Ca., 1988. Beckman, Frank S. “Mathematical Foundations of Programming”, Addison Wesley, 1981.
Unpublished Material
Canillo, Hazel. “Expresstrain: A computerbased Expression Trainer”, Asian College of Technology, 2002
Websites
Kornai, Andras. “Natural Languages and the Chomsky Heirarchy”, http://portal.acm.org/citation.cfm?id=976932#absract Wikipedia, The Free Encyclopedia. “The Theory of Computation”. http://en.wikipedia.org/wiki/Theory of computation Sukumar Nandi et al “Additive Cellular Automata: Theory and Applications,
http://as.wiley.com/WileyCDA/WileyTitle/productCd0818677171,subjectCdEE02.html Alur, Rajeev et al. “A Theory of Timed Automata”, http://citeeser.ist.psu.edu/alur94theory.html Gajic, B.S. “An Automata Theory Approach to Solving the Dynamic Task Allocation Problem in Distributed Computer Systems”, http://www.stephenwolfram.com/publications/articles/ca/84preface/5/text,html Boccara, N et al. “An Automata Network PredatorPrey Model with Pursuit and Evasion”, www.cse.msstate.edu/COURSES/graduate.html Mannevile, P. et.al. “Cellular Automata and Modeling of Complex physical Systems”, http://csemsstate.edu/COURSES/graduate.html Duchamp, Gerard et al. “Derivatives of Rational Expressions and Related Theorems”, http://portal.acm.org/citation.cfm?id=985569 Zaide, D. et al. “Canonical Derivatives, Partial Derivatives and Finite Automaton Constructions”, http://portal.acm.org/citation.cfm?id=637768
GLOSSARY OF TERMS
Abstraction. A concept or idea not associated with any specific instance. It defines an object in terms of its properties. Algorithm. A set of rules that a search engine uses to rank the listings contained within its index, in response to a particular query. Alphabet. A character set that includes letters and is used to write language. Automata. Plural form of automation. A machine of formal system designed to follow a precise sequence of instruction. Automata Theory. It includes the study of the capabilities and limitations of computing processes, the manner in which systems receive input, process it, and produce output, and the relationships between behavioral theories and the operations and use of automated devices. CAI. [Computer Aided Instruction] A program used as instructional material used in classroom instruction or any related activity. Compiler. A computer program that translates programs expressed in a highlevel language into their machine language equivalents. The compiler takes the finished source code listing as input and outputs the machine code instructions that the computer must have to execute the program. See: assembler, interpreter, crossassembler, crosscompiler. Computer. An electronic device used for storage and processing of information. Computer Science. The systematic study of computing systems and computation. The body of knowledge resulting
from this discipline and methods; design methodology, algorithms, and tools; methods for the testing of concepts; methods of analysis and verification; and knowledge representation and implementation. Computer System. It is set of hardware devices, software and people who use them for a specific purpose. Contextface Grammar. A formal grammar in which every production rule is of the form where V I a nonterminal symbol and w is a string consisting of terminals and/or nonterminals. The term “contextfree” comes from the fact that the nonterminal V can always be replaced by w, regardless of the context in which it occurs. A formal language is contextfree if there is a contextfree grammar that generates it. Deterministic Finite Automata. In the theory of computation, a deterministic finite state machine or deterministic finite automation (DFA) is a finite state machine where for each pair of state and input symbol there is a deterministic next state. FARE. Stands for Finite Automata and Regular Expression Generator, the name given to the developed software as an output if this study, and will be used as computer aided instruction tool. Finite Automata. A finite state machine (FSM) ot finite automation is a model of behavior composed of states, transitions and actions. A state stores information about the past, i.e. reflects the input changes from the system start to the present moment. A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition. An action is a description of an activity that is to be performed at a given moment. Finite state Machine. FSM’s are machines (generally computer program), which proceed in clearly separate and discrete steps from one to another of a finite number of configurations or states. There is a wellknown relationship between classes of language grammars and finite state machines, namely, that finite state machines are capable of recognizing regular grammars. Generator. The term given to a program module that serves as a component of the wole software. E.g. Regular Expression Generator. Machine. Common term for a computer program.
Machine Language. A program in the form of a series of binary codes that are understandable by the CPU. ((.9% of the time programmers write their code in another “higher level” programming language, which in turn translates their code into machine language. Model. A hypothetical description of a complex
entity or process. Parse Tree. A parse tree is the way the genetic programming paradigm represents the functions generated by a genetic program. A parse tree is similar to a binary decision tree and preorder traversal if the tree produces an Sexpression that represents a potential solution in reverse polish notation. Parser. A computer program that divides codes into functional components. Parsing. Parsing refers to the process by which programming data input is broken into smaller, more distinct chunks of information that can be more easily interpreted and acted upon. Polymorphism. It refers to a programming language’s ability to process objects differently depending on their data type or class. More specifically, it is the ability to redefine methods for derived classes. Recursive Function. In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are “computable” in some intuitive sense. In fact, in computability theory it is shown that the recursive functions are precisely the functions that can be computed by Turning machines. Recursive functions inductive definition (below) builds upon that of the primitive recursive functions. Regular Expression. It is a string that describes a whole set of strings, according to certain syntax rule. String evaluator. One of the components of the software that accepts input string and accepts its validity based on a given rule definition.
Appendix A
SAMPLE QUESTIONNAIRE
Dear student:
Warm Christian greetings!
The undersigned would like to determine the feasibility and effectiveness of the software he developed to help you and your instructors in teaching Automata Theory subject. The information he gets will be very useful in his thesis. In this regard, kindly answer the following questions. Thank you very much for your cooperation and assistance.
Amiably yours,
Leo C. Bermudez
A. Personal Information
1. Name__________________________________________
SurnameFirstname Middle Initial
2. Age______ Gender______
3. Course:______________________ Year Level:_______
4. Do you have Automata Theory subject? ○ Yes ○ No
5. If your answer in question number four is ye, how do you find the subject with regards to:
a. Its level if difficulty? (please check one)
○ Very difficult ○ difficult ○ Moderate
b. It’s being interesting to students?
○ Very interesting○ Interesting○ Boring
c. Its complexity?
○ Very complex ○ Complex ○Moderately complex
6. What particular topics in automata you find complicated? (You can write at most three)
_______________________________
_______________________________
_______________________________
B. The Need for Visual Aids to Facilitate Classroom Instruction
7. Does your teacher use visual aid during his/her discussions?○ Yes○ No
8. Do you think visual aids can facilitate classroom instructions? ○ Yes○ No
9. Which three topics listed in questions no. 5 you think the teacher should use visual aid?
a) ______________
b) ______________
c) ______________
10. How difficult it is to convert regular expressions to finite automata?
○ Very difficult ○ Difficult ○ Moderate
C. Software Effectiveness
11. Have you tried using FARE? ○ YES ○ NO
12. How do find the software in terms of its: (if you have tried using the FARE) a. Usefulness?
○ Very useful ○ Useful ○ Not so useful
b. Efficiency?
○ Very Efficient ○ Efficient ○ Not so efficient
c. Accuracy?
○ Very accurate ○ Accurate ○ Not so accurate
13. What is your rate of FARE from a scale of 1 to 10? ____ 14. How do you find Automata Theory subject after using FARE with regard to its level of difficulty? ○ Very difficult ○ Difficult○ Moderate
Appendix B
SAMPLE FORM OF STANDARD SOFTWARE TESTING PROCEDURES
Dear sir:
Warm Christian greetings!
The undersigned would like to determine the functionality and effectiveness of the software he developed based on the standard software Testing Procedures. This software is called Finite Automata and Regularly Expression aided instructional tool for Automata and rate it based on the following categories: stability, portability, dependability, efficiency, usability, and maintainability. Thank you very much for your cooperation and assistance.
Amiably yours,
————————————————
Leo C. Bermudez
Please rate the following categories from 1 (lowest) to 3 (highest). A. STABILITY TESTING
1. System Design _____
2. Software Used for Development _____
3. Modeling Tool Used _____
B. PORTABILITY TESTING
1. Program Portability _____
2. Data Portability _____
3. Enduser Portability _____
4. Developer Portability _____
5. Documentation Portability _____
C. DEPENDABILITY TESTING
1. Failure Detection _____
2. Anomaly Detection _____
D. EFFICIENCY TESTING
1. Correctness _____
2. Completeness _____
3. Conformity with the Requirements _____
E. USABILITY TESTING
1. Userfriendliness _____
2. Less Response Time _____
F. MAINTAINABILITY TESTING
1. Corrective Maintenance _____
2. Adaptive Maintenance _____
3. Preventative Maintenance _____
4. Perfective Maintenance _____
Appendix C
SAMPLE WEIGHTED MEAN COMPUTATION
Nature of the Subject According the Students
Item H(3) MH(2) Low(1) _X Verbal Description
Difficulty of the subject 25 11 3 2.56 H
Negative Interest Towards the Subject 20 13 6 2.35 MH Complexity of the Subject 28 8 3 2.64 H
Average 67 35 25 2.51 H
Difficulty of the Subject
WM = ∑WiXiN = 25(3)39+ 11(2)39+ 3(1)39
= 1.92 + 0.56 + 0.08
= 2.56
Negative interest towards the Subject
WM = ∑ WiXiN = 20(3)39+ 13(2)39+ 6(1)39
= 1.54 + 0.66+ 0.15
= 2.35
Complexity of the Subject
WM = ∑WiXiN = 28(3)39+ 8(2)39+ 3(1)39
= 2.15 + 0.41 + 0.08
= 2.64
Students’ Responses towards the Subject Using FARE
Item H(3) H(2) H(1) _X Verbal Description
Difficulty of the Subject 9 4 26 1.56 MH
Negative Interest Towards the Subject 7 5 27 1.49 L Complexity of the Subject 6 5 28 1.43 L
Average 22 14 81 1.49 L
Difficulty of the Subject
WM = ∑WiXiN = 9(3)39+ 4(2)39+ 26(1)39
= 0.69 + 0.20 + 0.67
= 1.56
Negative Interest towards the Subject
WM = ∑WiXiN = 7(3)39+ 5(2)39+ 27(1)39
= 0.54 + 0.26 + 0.69
= 1.49
Complexity of the Subject
WM = ∑WiXiN = 7(3)39+ 5(2)39+ 28(1)39
= 0.46 + 0.26 + 0.71
= 1.43
Appendix D
UML NOTATIONS USED
Use Case Diagram Notations
Use Case. It is a set of scenarios describing an interaction between a user and a system.
Actor. It represents a user o another system that will interact with the system you are modeling.
Boundary. It refers to the scope of the system.
Association Line. Also known as trigger, which refers to the interfacing or communication of the actor and the use case.
Class Diagram Notations
Class Name
Attributes
Methods
Class. It is collection of the same objects. It has three parts namely: the name, the attributes or properties, and the methods or functions.
Simple Association. It is an association used to relate two independent
classes. ♦Aggregation. It is association used to relate two classes where in one class is dependent from the other or one class is part of the other. Generalization. An association that is used to show inheritance. Sequence Diagram Notations
Actor. It represents a user or another system that will interact with the system you are modeling.
Object:Class
Class. Class roles describe the way an object will behave in contect. Use the UML object symbol to illustrate class roles, but don’t list object attributes.
Object:Class
Object:Class
Actor
Activation. Activation boxes represent the time an object needs to complete a task.
Activations
Object:Class
Object:Class
Actor
Messages. Messages are arrows that represent communication between objects. Use halfarrowed lines to represent asynchronous messages. Asynchronous messages are sent from an object that will not wait for a response from the receiver before continuing its tasks.
Object:Class
Object:Class
Actor
Lifelines. Li8felines are vertical dashed lines that indicate the object’s presence over time.
Lifelines
Appendix E
CODE SAMPLES
The proponent pasted some code samples of the program to let the users get some idea on how the program was created. This would help him make enhancements or even changes specially if there would be suggestions from knowledgeable users. Sample Code for Class CreateAlphabet
Public Class Alphabet
Private f_char As Char
Private s_char As Char
Public Property firstChar() as Char
Get
Return f_char
End get
Set(ByVal Value As Char)
F_char = Value
End Set
End property
Public Function CreateAlphabet() as String
Dim a As String
a = f_char & “,” & s_char
Return a
End Function
End Class
Sample Code for class EvaluateExpression
Public Class EvaluateExpression
‘ Legend:
‘+ = Logical OR operator
Private lst As New REList
Private myStr() As String
Private transitionTable As New transitionTable
Public Sub New()
End Sub
Public Sun New(ByVal strVal As String)
myStr = Split(strVal)
EvalStr()
End Sub
Private Function EvalStr() As String
‘declare variables
Dim i%,STATE%,RE$,LastPos%,SubStr%,TT$, ctr%, substring$
Lst = New REList
For i = 0 To UBound(myStr)
Select Case STATE
Case 0
Select Case myStr(i)
Case “accepts”
STATE = 1
Case “does”
Case “not”
Case “else”
STATE = 0
End Select
‘ accepts string that
Case 1
Select Case myStr(i)
Case “any”, “all”
STATE = 1
Case “string”, “words”
STATE = 3
Lst.AddLst(0, “(a+b)*”)
LstPos = 0
End Select
Case 2
‘ limit
Case 3
Select Case myStr(i)
Case “in”
STATE = 4
Case “that”
STATE = 3
Case “ends”, “end”, “ending”
STATE = 4
Case “starts”, “start”, “starting”
State = 5
Case “has”
State = 8
End Select
‘ending in . . . .
Case 4
Select Case myStr(i)
Case “even”
STATE = 15
Lst.RemoveAt(0)
Case “odd”
STATE = 16
Lst.RemoveAt(0)
Case “in”
STATE = 4
Case “or”
Lst.Addlst(Lst.Count, “ + ”)
LastPos = 2
STATE = 6
Case “and”
STATE = 14
Case Is <> “”
Lst.AddLst(1 + SubStr, myStr(i))
LastPos = 1
STATE = 4
End Select
‘ starting in . . . .
Case 5
Select Case myStr(i)
Case “in”
STATE = 5
Case “or”
Lst.AddLst(1, “ + ”)
LastPos = 1
STATE = 7
Case “and”
STATE = 13
Case Is <> “”
Lst.AddLst(0, myStr(i))
LastPos = 0
STATE = 5
End Select
Case 6 ‘ or from ends
Select Case myStr(i)
Case “ends”
STATE = 9
Case “starts”
STATE = 10
Case Is <> “”
Lst.AddLst(LastPos + 1, myStr(i))
STATE = 6
End Select
Case 7 ‘ or from starts
Select Case myStr(i)
Case “ends”
Lst.RemoveAt(LastPos)
STATE = 11
Lst.AddLst(Lst.Count, “ + “)
Case “starts”
Lst.RemoveAt(LastPos)
STATE = 12
Lst.AddLst(Lst.Count, “ + ”)
Case Is <> “”
Lst.AddLst(LastPos + 1, myStr(i))
STATE = 7
End Select
Case 8 “ substring
Select Case myStr(i)
Case “the”, “substring”
STATE = 8
Case Is <> “”
For ctr = 0 To Len(myStr(i)) – 1
substring &= myStr(i).Substring(ctr, 1) & “”
Next
Lst.AddLst(0, “(a+b)* ”& subString)
SubStr = 1
STATE = 3
End Select
Case 9 ‘ or ends in . . . .
Select Case myStr(i)
Case “in”
STATE = 9
Case Is <> “”
Lst.AddLst(Lst.Count,”(a+b)*”myStr(i))
STATE = 9
End Select
Case 10 ‘ or starts in . . . .
Select Case myStr(i)
Case “in”
STATE = 10
Case Is <> “”
Lst.AddLst(Lst.Count, myStr(i) & ” (a+b)*”)
STATE = 10
End Select
Case 11
Select Case myStr(i)
Case “in”
STATE = 11
Case Is <> “”
Lst.AddLst(Lst.Count, “(a+b)*” & myStr(i))
STATE = 11
End Select
Case 12
Select Case myStr(i)
Case “in”
STATE = 12
Case <> “”
Lst.AddLst(Lst.Count, myStr(i)&”(a+b)*”)
STATE = 12
End Select
Case 13 ‘ and from starts in
Select Case myStr(i)
Case “starts”, “starting”, “start”
MsgBox(“Conflict Statement”)
Exit Function
Case “ends”, “ending”, “end”, “in”
STATE = 13
Case <> “”
Lst.AddLst(Lst.Count, myStr(i))
STATE = 13
End Select
Case 14 ‘ and from ends in . . . .
Select Case myStr(i)
Case “ends”, “ending”, “end”
MsgBox(“Conflict Statement” & myStr(i))
Exit Function
Case “starts”, “starting”, “start”, “in”
STATE = 14
Case <> “”
Lst.AddLst(Lst.Count, myStr(i))
STATE = 14
End Select
Case 15 ‘ even
Select Case myStr(i)
Case “a”
Lst.AddLst(LastPos, “((b* a b*)(a b*))*”)
Case “b”
Lst.AddLst(LastPos, “((a* b a*)(b a*))*”)
End Select
STATE = 4
Case 16 ‘ add
Select Case myStr(i)
Case “a”
Lst.AddLst(LastPos, “((b* a b*)(a b*))*”)
Case “b”
Lst.AddLst(LastPos, “((a* b a*)(b a*))*”)
End Select
STATE = 4
End Select
Next
End Function
Private RE As String
Public Function showRegularExpression() As String
‘RE As String
RE = Lst.showRE()
transitionTable = New TransitionTable(RE)
Return RE
End Function
Public Function showTransitionTable(byVal index As Integer)As
String Return transition.ShowTransitionTable().Item(Index)
End Function
Public Function TransitionTableCollectionCount() as Integer
Return transition.ShowTransitionTable.Count
End Function
Public Function GetTransitionCollection() As Collection
Return transitionTable.GetTransitionCollection
End Function
End Class
Sample Code for REList
Public Class REList
Inherits CollectionBase
Public Sub New()
MyBase.New()
End Sub
Public Sub AdLst(ByVal indx As Integer, byVal val As Object)
‘ adds an item to list
If Me.List.Count = 0 then
Me.List.Add(val)
Else
If (Me.List.Count()1) >= indx Then
Me.List.Insert(indx, val)
Else
Me.List.Add(val)
End If
End If
End Sub
Public Function showRE() As String
Dim RegularExpression$, i%
For I = 0 To (Me.List.Count() – 1)
RegularExpression &= Me.List(i) & “ “
Next
Retrun RegularExpression
End Function
End Class