The Study of Computer Science and the Basics of Computer Science

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 one-shot 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 computer-aided 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 object-oriented 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 computer-aided 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 round-trip 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 to; 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 the 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 computershad bemathematicians w 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 grammar-like 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 Church-Turing 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:

•  which problems are unsolvable by a computer
• which problems are solvable by a computer, but require such an enormous long time to compute that the solution is impractical; and
• 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 problem-solving. Context-free grammars are used to specify programming language syntax. Non-deterministic pushdown automata are another formalism equivalent to context-free 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 star-closure,  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 lower-case 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 h is study entitled “An Automata Theory Approach to Solving the Dynamic TaskAllocation Problem in Distributed Computer Systems”,nboth 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 hands-on interaction.

Mr. Gajic further explained that an automata theory course can be taught in an interactive, hands-on 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 non-deterministic 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 computer-based 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 open-close 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 tobe 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 non-accept 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.

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 One-Dimensional Probabilistic Site-Exchange Cellular Automation, the effect of mixing one-dimensional 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 multiple-point-correlation approximation. By increasing the mixing, the order of the phase transition has been found to change from second order to first order. The tri-critical point has been located and estimates are given for the beta component. Short and long-range 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 computer-aided 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

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. A letter in the alphabet is also a regular expression denoting a set containing a one-letter 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.

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 context-free 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 code-generation. 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 fast-running 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.

Object-Oriented Programming Approach

This study uses object-oriented 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 object-oriented language, it uses classes and objects to show how each component relates to each other by which inheritance is applied. Other object-oriented 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 Context-Free 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 Object-based 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.

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 non-deterministic finite automata, parse trees, context-free 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 2005-2006 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 decision-making.

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 2005-2006. 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:

• without using the Finite Automata and Regular Expression Generator (FARE) software; and
• Using Finite Automata and Regular Expression Generator (FARE) software?
• How functional was the development Computer Aided Instruction tool as evaluated by:
• researcher based on Standardized Software Testing Procedures; and
• 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 one-shoot 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.

• 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 SOFTWAR\]

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. 2004-2005.
Founded on September 2, 1998 as a computer-training 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 short-term courses. Two years later, it offered the two-year 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 four-storey 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 Pre-school Department and then, much later on, the High
School Department. These departments were grouped together into one division – the Integrated School Division (ACT-ISD).

In 1997, another big event in the school’s history happened – the construction of the seven-storey Rodrigo A. Abellanosa building, which housed the school’s Physical Rehabilitation Center, its mini-auditorium, an outstanding Audio-Visual Center and the President’s Suite.

Just recently, in 2004, the school reorganized. To new academic departments were formed – the Institute of Medical Sciences (ACT-IMS), which offered two medical courses: BS in Physical Therapy and BS Nursing; and the Institute of Computer Studies (ACT-ICS), 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

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.

Students’ response to the given questionnaires without using Finite Automata and Regular Expression Generator.

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 2005-2006. 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

Legend: H-HighMH-Moderately HighL-Low
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 computer-aided 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)

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

Legend: H-HighMH-Moderately HighL-Low
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 computer-aided 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.

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 zero-risk, as reflected in Table 2.4. Since it is a computer-aided 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 user-friendliness 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 computer-aided 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 data-flow diagrams (DFD) to depict the different events triggered by the user. The other approach is the object-oriented 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 object-oriented 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.

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
Pre-condition: User wants to input characters to be used as alphabet of the language. Postcondition: 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
Pre-condition: 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: create R.E; 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
Pre-condition: 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
Pre-condition: 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. 3form 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
Pre-condition: 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
Pre-condition: String is compared to R.E.
Post condition: Evaluation result is displayed.

Steps:
UserSystem

1. create message window
2. if string is accepted then

Class Diagram

In Object-oriented 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.

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.

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.

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.  This is how the software works. The rule must start with the phrase “a language that accepts any string” followed by the rule description. 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

1. Ullman, Jeffrey et al. “Introduction to Automata Theory, Languages, and Computation”, Addison-Wesley, Reading, Massachusettes, 1979
2. Daniel A. Cohen, “Introduction to Computer Theory, 2nd Edition”, John Wiley & Sons, Inc. New York, 1997.
3. Harry R. Lewis and Christos H. Papadimitrou, “Elements of the Theory of Computation, 2nd Edition”, prentice Hall, New Jersey, 1998.
4. Fraser and Hansen, “A Retargetable C Compiler: Design and Implementation”, Benjamin/Cummings Publishing Company, Redwood City, Ca., 1995.
5. 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

1. Canillo, Hazel. “Expresstrain: A computer-based Expression Trainer”, Asian College of Technology, 2002

Websites

1. Kornai, Andras. “Natural Languages and the Chomsky Heirarchy”, http://portal.acm.org/citation.cfm?id=976932#absract
2. 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,
3. http://as.wiley.com/WileyCDA/WileyTitle/productCd-0818677171,subjectCd-EE02.html
4. 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/84-preface/5/text,html Boccara, N et al. “An Automata Network Predator-Prey
5. 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
6. 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

1. Abstraction. A concept or idea not associated with any specific instance. It defines an object in terms of its properties.
2. Algorithm. A set of rules that a search engine uses to rank the listings contained within its index, in response to a particular query.
3. Alphabet. A character set that includes letters and is used to write language.
4. Automata. Plural form of automation. A machine of formal system designed to follow a precise sequence of instruction.
5. 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.
6. Compiler. A computer program that translates programs expressed in a high-level 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, cross-assembler, cross-compiler.
7. Computer. An electronic device used for storage and processing of information.
8. 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.
9. Computer System. It is set of hardware devices, software and people who use them for a specific purpose.
10. Context-face Grammar. A formal grammar in which every production rule is of the form where V I a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. The term “context-free” comes from the fact that the non-terminal V can always be replaced by w, regardless of the context in which it occurs. A formal language is context-free if there is a context-free grammar that generates it.
11. 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.
12. 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.
13. 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.
14. 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 well-known relationship between classes of language grammars and finite state machines, namely, that finite state machines are capable of recognizing regular grammars.
15. Generator. The term given to a program module that serves as a component of the wole software. E.g. Regular Expression Generator.
16. Machine. Common term for a computer program.
17. 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.
18. Model. A hypothetical description of a complex entity or process.
19. 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 S-expression that represents a potential solution in reverse polish notation.
20. Parser. A computer program that divides codes into functional components.
21. 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.
22. 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.
23. 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.
24. 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.