Get help now

The Study of Computer Science and the Basics of Computer Science

  • Pages 51
  • Words 12526
  • Views 264
  • dovnload

    Download

    Cite

  • Pages 51
  • Words 12526
  • Views 264
  • Academic anxiety?

    Get original paper in 3 hours and nail the task

    Get your paper price

    124 experts online

    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; 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 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:
    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 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 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 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 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 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.

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

    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 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: 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 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. 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. 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
    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.49-3.00 High Students did not like the subject
    (H) have negative interest in
    learning the subject because of
    it’s complexity.

    1.60-2.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.00-1.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 Computer-Aided 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 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

    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: 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) 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: 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.

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

    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
    Pre-condition: 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
    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
    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
    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.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
    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
    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 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.

    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”, Addison-Wesley, 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 computer-based 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/productCd-0818677171,subjectCd-EE02.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/84-preface/5/text,html Boccara, N et al. “An Automata Network Predator-Prey 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 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. 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. 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. 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 well-known 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 S-expression 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. End-user 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. User-friendliness _____
    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 half-arrowed 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

    This essay was written by a fellow student. You may use it as a guide or sample for writing your own paper, but remember to cite it correctly. Don’t submit it as your own as it will be considered plagiarism.

    Need a custom essay sample written specially to meet your requirements?

    Choose skilled expert on your subject and get original paper with free plagiarism report

    Order custom paper Without paying upfront

    The Study of Computer Science and the Basics of Computer Science. (2016, Aug 27). Retrieved from https://graduateway.com/finite-automata-and-regular-expression-generator-aproposed-computer-adided-instruction-tool/

    Hi, my name is Amy 👋

    In case you can't find a relevant example, our professional writers are ready to help you write a unique paper. Just talk to our smart assistant Amy and she'll connect you with the best match.

    Get help with your paper