Educational Technology & Society 3(2) 2000
ISSN 1436-4522

Teaching Formal Languages by an Intelligent Tutoring System

Vladan Devedzic
Department of Information Systems
FON - School of Business Administration
University of Belgrade
POB 770, Jove Ilica 154, 11000 Belgrade, Yugoslavia

John Debenham
Key Centre for Advanced Computing Sciences
University of Technology, Sydney, PO Box 123
Broadway, NSW 2007, Australia

Dušan Popovic
"Mihailo Pupin" Institute
Automation Lab
Volgina 15, 11000 Belgrade, Yugoslavia


The paper describes design of the FLUTE system, an intelligent tutoring system in the domain of formal languages and automata. The basic idea of the FLUTE system is a systematic introduction of students into the system's domain, in accordance with both the logical structure of the domain and individual background knowledge and learning capabilities of each student. Other intelligent tutoring systems in that domain are not described in the open literature. The knowledge in the FLUTE system is represented starting from ITS ontology that has been defined within a recently developed framework and a model of intelligent tutoring systems, called GET-BITS. A brief overview of the model/framework is also included. The contents that should be presented to the student during tutoring sessions are discussed and logical organization of such contents within the system is described. The system is analyzed in the paper from the pedagogical point of view. Every concept that a student has to learn during a session with FLUTE, the system illustrates by a number of examples. This makes the tutoring process more dynamic and facilitates learning.

Keywords: Intelligent tutoring systems, Ontology, Formal language learning, Automata, GET-BITS

1. Introduction

A major problem for many students of computer science in adopting and mastering the material taught in the courses of formal languages and automata is a large number of abstract, complex, specific, and seemingly very similar concepts they have to learn. This leads to potential monotony and difficulties in capturing the essence and diversity of the concepts when the material is presented in the traditional way.

In order to make learning formal languages and automata more attractive for students and make the abstract material more concrete, development of an intelligent tutoring system (ITS) called FLUTE (Formal Languages and aUTomata Environment) has been started. The system design is based on the GET-BITS framework and model of ITS (GEneric Tools for Building ITS) (Devedzic et al., 1999).

This paper presents the design of the FLUTE system and analyzes the system's functionality from the pedagogical point of view. Section 2 defines the problem more precisely, and Section 3 briefly overviews the GET-BITS model. Some discussion on why have we developed FLUTE is provided in Section 4. In Section 5 the architecture of the FLUTE system is described and it is shown how different parts of knowledge are effectively represented and built in the knowledge base. Sections 6 through 8 present the analysis of the FLUTE system, showing its advantages and limitations.

2. Problem Statement

It is an ultimate goal of any ITS to make the learning process in the corresponding domain most effective. Careful selection of the contents, kinds and structure of knowledge, information and data to be built into the ITS is of an extreme importance in achieving that goal. In that sense, this paper describes:

  1. the overall architecture of the FLUTE system from the knowledge and data organization perspective;
  2. the structure of domain knowledge built in the system; all the important contents the student has to learn are specified, as well as possible paths that she/he can take in learning;
  3. how the domain knowledge is related to the necessary pedagogical knowledge and the student models;
  4. some details from FLUTE's cognitive support for the learner, as well as how the system tries to increase the learner's interest for further study of related topics;
  5. how the GET-BITS framework is used in designing the system from the ontology engineering perspective; and
  6. the role of numerous examples in illustrating each topic.

3. Previous Work

Other similar ITSs in the domain of formal languages and automata are not reported in the open literature. However, design of several other successful ITSs in different domains of computer science (Anderson et al., 1990; Johnson, 1990; Matsuda et al., 1997), as well as of some other ITSs from related areas (Chee and Xu, 1997; Herzog, 1997; Katz and Lesgold, 1993; Kong, 1994; Wong et al., 1996) has helped in designing the FLUTE system. In formulating the domain knowledge that should be built into the FLUTE system several textbooks on formal languages and automata, such as (Hopcroft and Ullman, 1979) or (Revesz, 1983), were consulted. The structures of some relevant university courses and the experience of several human instructors teaching formal languages at the university level were also considered. Since one of the project ideas was that the FLUTE system should be practically oriented, i.e. to represent knowledge that can be practically applied, literature on compilers and compiler writing (Appel, 1998; Fischer, 1988; and Muchnick, 1997) has also been used.

In developing FLUTE, we have used the GET-BITS framework (Devedzic et al., 1999). The heart of the framework is our view of the ITS ontology as a layered, hierarchical scheme of composition of constituent parts - components and agents - of any ITS, shown in Figure 1. All agents and components in an ITS are defined at one of five levels of abstraction, and along several dimensions (such as knowledge representation, methods, and inference techniques). Primitives are components like plain text, logical expressions, attributes and numerical values. They are used to compose units like rules, frames, and different utility functions. These are then used as parts of certain building blocks that exist in every ITS, e.g. topics, lessons and teaching strategies. At the system level, we have self-contained systems or agents like explanation planners, student-modeling agents, and learning actors, all composed using different building blocks. Finally, at the integration level there are collaborative learning systems, distributed learning environments, and Web-based tutoring systems.

Figure 1. Layers and dimensions of the ITS ontology in the GET-BITS approach

The integrated concept of the ITS ontology is split in GET-BITS into a number of separate but interrelated ontologies for all constituent parts of an ITS, such as System ontology, Domain knowledge ontology, Pedagogical knowledge ontology, Student model ontology, and Interface ontology. These ontologies are defined in small composable modules at each level of abstraction and using the top-down approach, so that the knowledge they need can be assembled. All ontologies have the same starting point (the root concept) defined as an abstract knowledge element (Devedzic and Radovic, 1999). It reflects the possibility of representing all data, information and knowledge in an intelligent system in a unified way (Debenham, 1998). In this way, each ontology assigned to a higher level of abstraction includes the taxonomies of the lower levels, and forms a set of inclusion lattices of ontologies.

4. Motivation - Why Teaching Formal Languages by an ITS?

While studying formal languages is essential in theoretical computer science, experience of several human instructors shows that teaching such courses to students of computer engineering often causes some practical problems. Such students typically want "concrete things", frequently get bored when they "cannot examine the material by the keyboard and the mouse", and usually feel hard to master the subject because "everything looks alike". Of course, these phrases may also reveal deficiencies in the instructor's capability to transfer the relevant knowledge in an appropriate way. However, since students of computer engineering are generally practically oriented, it is usually desirable for them to have some software to "play with" and simultaneously learn about formal languages and their importance in practical software engineering.

We have also found that the students' motivation for learning about formal languages increases if they know at any moment where exactly they can apply the knowledge they acquire. Their interest increases if somebody always tells them in what other disciplines grammars, parsers and automata are important. They get a better feeling for such concepts if they are illustrated in compiler design, or even in more advanced domains, such as designing adaptive screen forms (Valente et al., 1999) or development of ontologies (Lopez et al., 1999). On the other hand, it is not always easy to cover all such practical aspects in teaching a classical course on formal languages.

These observations have led us to the idea of developing FLUTE. The starting points in our conceptualization of the FLUTE system have been to develop an ITS that will help the students of computer engineering study the field of formal languages individually, help them learn efficiently and dynamically, and also help them in starting to explore related fields themselves.

5. Architecture of the FLUTE System

The architecture of the FLUTE system is shown in Figure 2. Note that the figure only stresses the details relevant for this paper, i.e. the nature and kinds of knowledge and data in the system. It doesn't show explicitly the active components of the modules (things like planners, inference mechanisms, example generators, exercise generators, etc.) and submodules of the individual modules. Student administration module, also omitted from Figure 2, maintains a database of students (users of the FLUTE system), records the current status of their knowledge and progress, handles student registration, and can be accessed directly through the user interface module.

Figure 2. Architecture of the FLUTE system

5.1. Expert Module

The Expert module contains domain knowledge and is organized according to the GET-BITS' Domain knowledge ontology. Figure 2 shows three most relevant parts of domain knowledge used in the FLUTE system. The first part contains all the concepts, topics, facts, procedural knowledge and domain heuristics the student has to learn. A meaningful subset of such items can be logically organized as a lesson. Items in a lesson are closely coupled but they can refer to items in other lessons. Some important attributes of each lesson are sets of objectives and goals, sets of topics, concepts, facts, theorems, etc. taught in that lesson, a set of the corresponding teaching rules, and a set of associated problems (tests, questions and exercises). An example is shown in Table 1 and Figure 3. Note that rules, problems and examples can be associated with both level 3 and level 4 items in Figure 1.

A major difficulty in mastering the basics of formal languages and automata is the domain's inherent abstractness. The best way to overcome it is to use a number of examples to illustrate all the concepts, principles and theory of the domain. Hence an essential component of domain knowledge is a database of examples (see Figure 2), which are systematically associated with every topic, concept, etc. that a student has to learn during a session. Presenting examples to the student is under the control of the system's pedagogical module. This makes the tutoring process more dynamic and facilitates learning.

It should be noted in Figure 2 that the pedagogical structure of the domain is considered a part of the domain knowledge rather than a part of the pedagogical module. This idea is not new, and has been simply transferred to the GET-BITS' Domain knowledge ontology from other successful ITSs (e.g., see Vassileva, 1990). It makes possible to separate all of the domain-dependent knowledge, stored within the expert module, from the other kinds of knowledge (i.e., from domain-independent pedagogical and explanation strategies and student model). Pedagogical structure of the domain is defined in FLUTE as a set of directed graphs showing explicitly precedence relationships of knowledge units within each lesson and among the topics of different lessons.






Derivation trees


Objective; Goal

Redundancy of grammars;

Obtaining reduced grammar



Redundant grammar


Concept; Fact;


Inactive (dead) symbol;

Redundant grammar contains unnecessary nonterminal symbols

Pumping lemma

Table 1. Hierarchy of items in a lesson

Rule D98:If a context-free grammar is reduced,
Then it contains no inactive symbols.
Problem P112:Find a reduced grammar that is
equivalent to the context-free grammar ~E123
Example E123:G = ({S,A,B,C}, {a,b,c}, S, F), F = {...}

Figure 3. A rule, a problem, and an example grammar

Such a dependency graph, defining the entire domain of the FLUTE system, is shown in Figure 4. In fact, that graph represents the top-level structure of the domain-specific ontology of formal languages and automata. It defines subjects of learning and possible learning paths in the domain. Wherever there is a fork in the path, the learning process can go either way. Wherever there is a join of two paths, the learning process cannot be continued unless the student has proved to master the knowledge along both paths (this is checked by the pedagogical module and is recorded in the student model). There are four learning levels: preliminaries, basic level, senior level, and advanced level. They must be passed in strict sequence. One of the parameters of the student model is the learning level, reflecting the student's background knowledge. Pedagogical module periodically and automatically tests the student to check her/his mastery of domain knowledge at the associated learning level.

A set of lessons is associated with every subject in Figure 4. For example, the subject of context-free grammars (CFG) is taught in the following set of lessons: derivation trees, normal forms, linear CFG, regular expressions and special types of CFG. Lessons of such a set are also treated as nodes of a dependency graph, hence precedence relationships for teaching lessons related to a subject are specified explicitly within the ontology of formal languages and automata.

5.2. Student Model

Student model in FLUTE is derived from components that make up the GET-BITS' Student model ontology. The components reflect:

  • the state of the student's current knowledge (a combination of one of the four learning levels and one or more "points" on a path (paths) at that level);
  • the student's current progress in learning a particular lesson ("point(s)" in the lesson's dependency graph);
  • timing and frequency of trying various exercises and asking for hints, explanations, and help;
  • the student's performance in answering the system's questions and solving problems (grades and timing, as well as the ratio of correct and incorrect answers); an important part of it is a degree of remembering "old" lessons (answers to questions from the lessons learned during previous sessions);
  • the student's learning behavior (frequencies of following correct/incorrect paths in learning a topic or a concept);
  • measures of how continuously and how frequently the student learns from the system;
  • measures of the student's initiative in working with the system (e.g., how many times the student has tried the restricted option of including a new example in the knowledge base, or how often she/he consults the links to related topics).

Figure 4. Pedagogical structure of the domain
(CFG - Context-Free Grammars; CSG - Context-Sensitive Grammars; DCFL - Deterministic Context-Free Lang.)

The values of the attributes are calculated from applying a set of rules and simple functions from the pedagogical module to a set of parameters that the system acquires and updates automatically during each session. Some of the parameters are indicated in parentheses in the above descriptions of the attributes. All of these activities are performed by the student-modeling agent, which is a part of the Student model ontology. The student model is saved after each session and is used in the beginning of the next session. If a student is having a session with FLUTE for the first time, the student-modeling agent gives her/him a set of exercises and tests before the tutoring process starts. In this way the student-modeling agent estimates the new student's background knowledge and determines initial values of the attributes of the student model. The knowledge that drives the operation of the student-modeling agent in updating the student model is encoded in the student model rules.

Although it is the task of the student-modeling agent to update and maintain the student model, users with special privileges (human instructors) can also modify the student model themselves.

5.3. Pedagogical Module

FLUTE always operates in one of the following three modes of operation: teaching, examination, and consulting. It is actually the pedagogical module that runs one of the corresponding pedagogical agents at any time, thus causing FLUTE to operate in one of these three modes.

When the teaching mode agent runs, FLUTE presents a lesson to the student. In the beginning, the agent executes a dedicated rule-based planner (called the lesson presentation planner) and develops an initial plan of teaching actions. The plan is based on the contents of the lesson being presented, the relevant dependency graphs and the student model. The plan actually represents a detailed outline of the lesson presentation. The strategy of Raymond and Pilon (Raymond and Pilon, 1994) is used for guiding the plan generation: each objective of the lesson being presented is decomposed into a number of transparencies, each one of them roughly corresponding to one concept, fact, procedure or theorem. Each transparency is set up of several pedagogical points, covering the item contained in that transparency. Starting from the initial plan, the teaching agent runs the lesson presentation planner again and generates sub-plans for presenting the lesson's objectives, topics, concepts, etc. Interaction with the student in teaching mode is provided through a set of buttons and dialog boxes. Depending on the student's reactions, the student-modeling agent regularly updates the student model (attributes like current progress, learning behavior, average speed of mastering lessons, etc.). The teaching agent communicates with the student-modeling agent and can change the sub-plans and possibly the entire lesson presentation plan if necessary. The two agents communicate easily by sharing their knowledge through the GET-BITS' Pedagogical knowledge ontology and Student model ontology.

In the examination mode, FLUTE's examination agent can generate problems and exercises for the student, offer hints and suggestions for problem solving, and conduct a more complex assessment of her/his knowledge through a systematic series of tests and examinations. After each examination session, no matter how complex it was, the examination agent sends request to the student-modeling agent to update the relevant attributes of the student model (grades, answering speed, current progress, etc.). Then it generates a plan of remedial actions and presents it to the student in the form of suggestions for further sessions and learning. All of the questions, problems, and exercises are designed as parts of examples in the corresponding database of examples, which is a part of the expert module. The pedagogical module differs between illustrative examples (used mostly by teaching and consulting agents) and test examples, and can store and retrieve past exams and tests on student's request.

The consulting mode agent is the one that answers the student's questions, explains domain concepts and heuristics, repeats required parts of any lesson corresponding to the student's current knowledge (as recorded in the student model), refines problem solutions, provides hints for further learning, etc. In this mode, the pedagogical module frequently transfers its control to the explanation module. The consulting mode is entered strictly on request. The consulting agent can send the student-modeling agent a request to alter the values of some attributes of the student model in this mode as well, but the timing functions are turned off. The student's initiative is considered most relevant in this mode and is calculated by dedicated functions.

Under the control of a human instructor, the student can extend the example database by a new example. Although there is no automatic recognition of the type, quality and relevance of the newly included example, this is a very useful way of extending the system's knowledge during the sessions themselves. Also, all three pedagogical agents often refer the student to related topics to explore them individually.

The core of knowledge that pedagogical agents rely on is the Pedagogical knowledge ontology, which defines the following sets of rules:

  • lesson presentation rules (rules of the lesson presentation planner)
  • remedial rules (rules of the remedial actions planner)
  • diagnostic rules (for evaluating the student's knowledge and understanding of topics, concepts, etc.)
  • didactic rules (defining the presentation's "look-and-feel" such as pointing, highlighting, underlining,...)
  • control rules (a kind of meta rules for the overall control of the pedagogical module operation)

Figure 5 shows an example of a diagnostic rule (PD8) and of a control rule (PC6):

Rule PD8:If test-score > 55 then set passed-test.
Rule PC6:If passed-test then calculate grade.

Figure 5. Examples of pedagogical rules

5.4.Explanation Module

FLUTE's explanation module is a user-oriented, rule-based agent, using all the available information from the domain knowledge base (contents of lessons, objectives, topics, dependency graphs and examples), as well as from the student model, in order to answer the student's questions and provide desired explanations. Specifically, it is designed to accept a request for explanation from the student and to do the following in response:

  • determine the contents of the answer/explanation;
  • decide upon the explanation presentation style (level of details, hints, augmentation material to be included, e.g., illustrations, examples, pointers to related concepts and references, etc., depending on the question itself and on the values of relevant parameters of the student model such as current knowledge, current progress, performance);
  • select the knowledge model that provides the easiest explanation in cases when multiple knowledge models can be used (e.g., select what formalism to use in the explanation if something can be explained both by CFG and automata);
  • compose the explanation and order its statements in a coherent, reasonable and comprehensible way.

The questions the student can ask are selected from a context-sensitive menu (Why, How, What If, Related Topic, Illustration, and More Explanation).

The explanation module is described in more details in (Devedzic et al., 1999).

5.5. User Interface

The user interface of the FLUTE system has been developed after the GET-BITS Interface ontology. It provides knowledge browsers and navigation tools, showing dependency graphs, lesson and course outlines, previous/next/arbitrary objective, transparency or pedagogical point, etc., and parameters of the student model (current knowledge and current progress such as "positions" within the corresponding dependency graphs, performance, learning behavior,...).

Students are allowed to use only a subset of the system's options. The user interface shows the other, restricted subset of options only to privileged users (human instructors). Restricted options allow the user to modify and update the contents of the knowledge base and (re)structure lessons through a set of specialized knowledge editors and browsers, thus enabling a rudimentary knowledge acquisition. They also allow for manual modifications of the student models.

We also plan to provide several other general-purpose tools of the user interface (notepad for student's notes, sound and light signals, color, markers, intensity, zooming, and other visual indicators, timer, context-sensitive on-line help, etc.).

6. Implementation and Examples

The FLUTE system has been implemented as a Windows 98 application, using MS Visual C++. It is designed as a single-user system, i.e. as an individual learning tool. At the moment we do not plan to extend it to operate as a collaborative learning tool or a Web-based ITS.

A session with FLUTE starts with the student's identification, which is followed by showing the student a brief summary of the part of the curriculum that she/he has supposedly mastered so far. The student can also see the values of relevant parameters of the student model that has been saved after the previous session has been completed. Then she/he is supposed to select one of the three modes of operation (teaching, examination, or consulting).

Let's assume that the student has selected the teaching mode. FLUTE allows the student to go again through the lessons that she/he has already learned, or to select some new material to learn about. In the later case, the material that the student can select is restricted according to the domain-specific ontology (see the dependency graph in Figure 4). An example of such a selection is shown in Figure 6. The student is supposed to select a field supported by the contents of the curriculum and a set of possible topics corresponding to that field. Every such a selection reflects a fork in the dependency graph at a certain level of details. In this example, the student has selected to learn a new lesson about grammars of formal languages, and has expressed the wish to learn more about the classes of grammars. In response, FLUTE consults the curriculum and the student model again and suggests a lesson to learn next. The student can review the lesson presentation plan if she/he wants to see its details prior to starting to learn. In some cases, the student may ask FLUTE to suggest an alternative lesson if she/he concludes that the current one doesn't suit their current learning goals.

Figure 6. Selecting the field (contents) and the corresponding topics to learn about

When the student starts learning a lesson, its presentation is done according to the lesson presentation plan. At fixed points in the plan, the student can switch to the examination or consulting modes. If, for example, the student learns about the elements of CFGs, FLUTE may generate an exercise as in Figure 7. In the exercise, FLUTE shows an example of a CFG and allows the student to perform some limited editing of the grammar's rules. The student can then try to answer some questions about the properties of the resulting grammar.

Figure 8 shows an example of how the student might answer a FLUTE's question in the examination mode of operation. The question is about the elements of the definition of automata. The student is supposed to assemble the correct list of basic elements of the definition of automata, starting from a larger list that contains redundant elements as well.

Finally, Figure 9 shows an example of using FLUTE in consulting mode. In the example, the student is supposed to have come to a point (within a lesson) at which it is possible to demand explanations from the system. The explanation she/he requires is of type "Illustration", and it has to clarify the process of translating a grammar's derivation rules. Note that the process of explanation is highly interactive: the student can "discuss" the explanation with FLUTE by editing some parts of the illustration, asking the system to solve the problem again, and the like.

Figure 7. An exercise about grammar rules

Figure 8. Answering a question about the definition of automata

Figure 9. Translating derivation rules (consulting mode)

7. Assumptions and Constraints

Once a student reaches a certain knowledge/learning level and the system assigns her/him certain appropriate knowledge and progress indicators, it is assumed that the students knows everything (i.e., she/he can apply every domain-dependent rule) before the corresponding point on the relevant dependency graphs. It depends on the pedagogical agents to decide when and how to check the student's current knowledge and whether to return her/him to a previous point or learning level if her/his performance is not satisfactory.

FLUTE is neither multimedia system nor a hypertext system, although in the analysis below it is compared to some multimedia and hypertext supported ITS.

Only the first two learning levels from Figure 4 are currently implemented (see Devedzic et al., 1999 for details of the implementation). The rules (knowledge) of the pedagogical and explanation agents/modules are still subject to change. To develop the whole system is an extremely complex task, and it should be noted that several potentially useful add-ons were omitted from the current design for the sake of reduced complexity. They include parsing and analysis of newly included examples, case-based reasoning, analogical reasoning, concept generalization, and many more.

8. Analysis and Evaluation

In this Section, FLUTE is analyzed from the pedagogical point of view and is informally compared to some other ITSs that have been used as referent systems in designing it. FLUTE's advantages are clearly shown.

8.1. Cognitive support and motivation

FLUTE's users are supposed to be adults - students of computer engineering who have their specific learning goals. In designing FLUTE we have tried to pay maximum attention to that specific group of potential users. Also, FLUTE does not provide support for collaborative learning. These two facts have guided our decisions on what kind of cognitive support and motivation FLUTE should provide.

We have treated the motivation issue in a rather traditional and restrictive way, as a combination of factors like the learner's curiosity, competition, challenge, control and confidence. See (Issroff and Del Soldato, 1996; Keller, 1987; and Lepper et al., 1993) for more elaborated discussions on the effect these factors have on learning. In brief, FLUTE always tries to create the learner's feelings of self-improvement and self-esteem in learning. We also want the FLUTE's users to have a feeling of getting rewarded for "winning in competing with the system". Whenever it is possible and appropriate, FLUTE lets the learners know there are more interesting issues and possibilities of applying the knowledge they acquire from the system. FLUTE's pedagogical agents combine the "Learner in control" and "System in control (Guidance)" approaches to instruction. Most users in the target group prefer the "Learner in control" philosophy, but novice students always need some guidance. During a learning session, FLUTE's pedagogical agents care about increasing/maintaining the learner's confidence by occasionally showing her/his progress factor from the student model. For example, after a successful completion of an exercise such as the one shown in Figure 7, FLUTE will occasionally (but not always!) show an indicator of improvement, taken from the student model. This action is related to the recognition that confidence is related to the perception of self-efficacy (Keller, 1987).

FLUTE is not a replacement for human instructor. It is a tool that helps students in learning individually about formal languages and automata. It doesn't simply transfer all of the built-in knowledge to the student - the idea is that it helps the student gradually and individually develop her/his knowledge and cognitive skills in that domain.

The built-in knowledge is, of course, limited. Therefore selected knowledge items in the knowledge base (lessons, topics, concepts, and examples) contain pointers to some references and related topics. These are shown to the student either on request, or when the pedagogical agents decide it could be helpful, or when they exhaust the other teaching possibilities. We have found such pointers to be extremely important for maintaining the students' interest at an acceptable level. For example, after completing the lessons and a set of examples treating CFGs, the student gets congratulations from FLUTE and can also see some additional material and references showing how CFGs are used in compiler design, design of adaptive screen forms, and ontology design. This way, practically oriented students get an immediate feeling of the purpose and benefits of learning such abstract things as formal languages and automata. It is a state in their minds that is difficult to measure, but is easily recognized and is often described by the students' words like: "Although much of the teaching material looks alike, I am curious about what will be the next pointer." In fact, some students are waiting for such pointers as if they were a reward.

In all three modes of operation, FLUTE's pedagogical agents occasionally perform some actions in order to increase the learner's curiosity, attention and interest. These actions include encouraging the learner to try more examples, showing useful pointers, explaining why something is good/useful to know, expressing disagreement if the learner's actions show that she/he is heading in wrong direction, complimenting the learner's success in doing exercises, and the like. Such actions have nothing to do with the teaching material itself. However, they are very important for getting the learners motivated and increasing their receptiveness or alertness, both of which are important parts of the system's functionality. They also increase the learners' curiosity and urge to ask for additional explanations. Other authors have performed more extensive studies of such issues (Issroff and Del Soldato, 1996; Mizoguchi et al., 1996; Murray, 1997). We have used their results in designing the FLUTE's pedagogical agents. However, there is a shortcoming in our current design in this regard: we don't use emotional pedagogical agents in the current implementation. There is evidence that such agents can greatly increase the learner's interest, motivation and attention (Rist et al., 1997).

We have also used some other ideas from (Mizoguchi et al., 1996), such as the idea of developing the learner's domain-dependent capabilities through gradually building her/his understanding of domain concepts, improving her/his problem-solving capabilities in the domain, and enhancing her/his skills. For example, FLUTE's examination mode agent is instructed to exercise the student by first asking her/him to solve easy problems, including a typical problem-solving schema of the related topic (i.e., an "expected" problem). More difficult problems include using a known schema, i.e. a schema that the student is supposed to have already used before. FLUTE doesn't support modifying an existing problem-solving schema, combining several schemata, and creating a new schema. In helping the student solve a problem, FLUTE can make analogies between known and unknown topics in the domain, in order to increase curiosity and stimulate individual motivation.

In order to illustrate the cognitive support that FLUTE offers to the student by a practical example, consider solving the problem represented in Figure 8. Let's assume that the question about the elements of the definition of automata is a typical question to ask the student after she/he has completed a corresponding lesson in the teaching mode. Before asking the student the question, the examination agent checks with the student-modeling agent to ensure that the student's current knowledge is sufficient for answering such a question. In the beginning, the student is let alone to try to solve the problem. She/He is allowed to ask for a hint, and the examination agent will offer a hint if it notices that the student is making a mistake when selecting the elements of the definition of automata from the window on the right-hand part of the screen.

Accepting the hint or asking for one enables many additional options which were disabled before the hint. We have built these options into the FLUTE's examination agent starting from the suggestions from (Murray, 1997). First, the student can suspend solving the problem and request to learn/review prior or prerequisite knowledge. Also, the examination agent can decide out of its own initiative to relate the problem to the student's prior knowledge, to remind the student what she/he already knows, to summarize/review prior knowledge, to test prerequisite knowledge and remedy it if necessary. The student is allowed to take initiative, switch to the consulting mode, ask questions, and ask for another similar problem in order to make analogies if possible. FLUTE might decide to give an analogy, or show an example, or tell what is relevant or what to ignore. In the example from Figure 8, suppose the student has already learned about grammars. FLUTE can relate the problem of automata definition to the problem of definition of grammars. It may also show analogies between terminal/nonterminal symbols of a grammar and input alphabet/states of an automaton. The student can switch back to the problem at any time and try to solve it. In the case of success, FLUTE will congratulate the student (but not too affectively - the students are skilled adults), encourage her/him to try more exercises (e.g. definitions of some specific kind of automata), and possibly show some useful pointers and the student's progress indicator. Otherwise, FLUTE will reveal the correct answer, explain what it believes the student needs to know in order to assemble the definition of automata correctly, and suggest to remediate the erroneous knowledge or missing knowledge. The suggestion will often require switching to the teaching mode. In both cases FLUTE shows some short summary of the problem/exercise in the end. The summary contains the success indicator, the statement about the problem type, the statement about the problem-solving method used, and suggestions for further learning process.

8.2. Evaluation Criteria

Pedagogical aspects and design suitability were the most important criteria used for the analysis and evaluation of FLUTE in comparison with other ITSs. The other criteria used were design flexibility (modularity, reusability and portability), ease of use, and flexibility of the student model. The results are briefly shown below.

8.3. Comparing FLUTE to some other systems

We have used several other ITSs as referent systems in developing FLUTE. Some of them are described in Katz and Lesgold (1993), Kong (1994), Vassileva (1990), and Wong et al. (1996). The main conceptual and design difference between FLUTE and such systems is that FLUTE has been developed after a thorough ontological analysis and with the help of previously developed GET-BITS framework. When FLUTE is compared to these other ITSs, its advantages come from:

  • the systematic design, based on the GET-BITS model and framework;
  • its explicit, highly modular, and extremely flexible model of domain knowledge; it is open and easy for extensions, since several new inputs can be added to any dependency graph; occasionally a new output from a graph can be generated (for example, another advanced topic can be added at the advanced level in Figure 4);
  • its strong, knowledge-based lesson presentation and didactic components (the way and time it shows lesson outlines, objectives, transparencies, etc., always depends on the student's recent reactions and the student model);
  • its knowledge-based and student-model-based deduction on the moments when the student must undergo exercises regarding both current lesson and past lessons;
  • several different ways and levels of assessment of the student's knowledge (questions, exercises, tests, etc.);
  • supporting timing functions in the examination and teaching modes, which is reflected in the student model;
  • the way it switches between three different modes of operation, both on the user's request and automatically, when the pedagogical module decides it is necessary;
  • its user-oriented, separate explanation module;
  • the way it treats examples (the role of examples is stressed in all three modes of operation, which makes the learning process much easier and more attractive); and
  • its more refined student model, allowing for more appropriate representation of student's knowledge and learning capabilities.

FLUTE's pedagogical module has been designed starting from the variants of the coach model used in the systems described in Vassileva (1990) and Wong et al. (1996), but with additional features described in Section 4.

Most apparent limitations and deficiencies of FLUTE's design with respect to the design of the other ITSs mentioned above are the lack of hypertext support, the lack of histories of past lessons, learning, and assessments in the student model, and weak example classification.

9. Conclusions

Design of FLUTE, an intelligent tutoring system in the domain of formal languages and automata, is featured by an explicit, flexible and easily extensible model of domain knowledge, three modes of operation (teaching, examination, and consultation), highly refined student model, and an extensible database of examples that facilitate both learning and tutoring processes. Domain-dependent pedagogical knowledge is included in the expert module, rather than in the pedagogical module, and the explanation facility is separated from the pedagogical module and constitutes a separate module in the system's architecture. The main advantages of such design are improved lesson presentation and knowledge maintenance, as well as more explicit distinction between different pedagogical features. The design is based on GET-BITS, an ontology-based framework for building intelligent tutoring systems, and can be used for developing other intelligent tutoring systems as well.

There are several directions in future research and further development of the FLUTE system:

  • development of appropriate techniques for knowledge simplification and maintenance, since the knowledge base in the expert module is upgraded time after time;
  • development of an automatic classifier of the examples in the database; such a classifier should be based on both the domain knowledge and the pedagogical knowledge;
  • development of a case-based generator of new problems for students, starting from the database of examples and incomplete input data.

10. References

  • Anderson, J. R., Boyle, C. F., Corbett, A. T. and Lewis, M. W. (1990). Cognitive Modelling and Intelligent Tutoring. Artificial Intelligence, 42 (1), 7-49.
  • Appel, A. W. (1998). Modern Compiler Implementation in Java. Cambridge, MA: Cambridge University Press.
  • Chee, Y. S. & Xu, S. (1997). SIPLeS: Supporting Intermediate Smalltalk Programming through Goal-based Learning Scenarios. In du Boulay, B., Mizoguchi, R. (Eds.) Artificial Intelligence in Education, Amsterdam: IOS Press, 95-102.
  • Debenham, J. K. (1998). Knowledge Engineering - Unifying Knowledge Base and Database Design. Berlin: Springer-Verlag.
  • Devedzic, V. & Radovic, D. (1999). A Framework for Building Intelligent Manufacturing Systems. IEEE Transactions on Systems, Man, and Cybernetics, Part C - Applications and Reviews. 29 (3), 422-439.
  • Devedzic, V., Radovic, D. & Jerinic, L. (in press). The GET-BITS Model of Intelligent Tutoring Systems. International Journal of Continuing Engineering Education and Life-Long Learning, Special Issue on Intelligent Systems/Tools in Training and Life-Long Learning.
  • Fischer, C. N. & LeBlanc, R. J. (1988). Crafting a Compiler. New York: Benjamin/Cummings Publishing Company.
  • Herzog, C. (1997). Cooperation and Competition of Sysntax-Oriented and Execution-Oriented Problem Solvers in Intelligent Programming Tutors. In du Boulay, B., Mizoguchi, R. (Eds.): Artificial Intelligence in Education, Amsterdam: IOS Press, 309-316.
  • Hopcroft, J. E. & Ullman, J. D. (1979). Introduction to Automata Theory, Languages and Computation. Reading, Massachusetts: Addison-Wesley.
  • Johnson, W. L. (1990). Understanding and Debugging Novice Programs. Artificial Intelligence, 42 (1), 51-97.
  • Issroff, K. & del Soldato, T. (1996). Incorporating Motivation into Computer-supported Collaborative Learning. In Proceedings of The European Conference on Artificial Intelligence in Education, Lisbon: Edicoes Colibri, 284-290.
  • Katz, S. & Lesgold, A. (1993). The Role of the Tutor in Computer-Based Collaborative Learning Situations. In: S. Lajoie and S. Derry (Eds.) Computers as Cognitive Tools, Hillsdale, NJ: Lawrence Erlbaum Associates, 289-317.
  • Keller, J. M. (1987). Strategies for Stimulating the Motivation to Learn. Performance and Instruction, 26 (8), 1-7.
  • Kong, H. P. (1994). An Intelligent, Multimedia-Supported Instructional System. Expert Systems with Applications, 7 (3), 451-465.
  • Lepper, M. R., Woolverton, M., Mumme, D. L. & Gurtner, J. (1993). Motivational Techniques of Expert Tutors: Lessons for the Design of Computer-Based Tutors. In S. Lajoie and S. Derry (Eds.) Computers as Cognitive Tools, Hillsdale, NJ: Lawrence Erlbaum Associates, 75-105.
  • Lopez, M. F., Gomez-Perez, A., Sierra, J. P. & Sierra, A. P. (1999). Building a Chemical Ontology Using Methontlogy and the Ontlogy Design Environment. IEEE Intelligent Systems, 14 (1), 27-36.
  • Matsuda, N., Kashihara, A., Hirashima, T. & Toyoda, J. (1997). An Instructional System for Behavior-Based Recursive Programming. In du Boulay, B., Mizoguchi, R. (Eds.) Artificial Intelligence in Education, Amsterdam: IOS Press, 325-330.
  • Mizoguchi, R., Sinitsa, K. & Ikeda, M. (1996). Task Ontology Design for Intelligent Educational/Training Systems. Paper presented at the Workshop "Architectures and Methods for Designing Cost-Effective and Reusable ITSs". Montreal, Canada, June 12-14, 1996.
  • Muchnick, S. (1997). Advanced Compiler Design and Implementation. Morgan-Kaufman Publishers.
  • Murray, T. (1997). Toward a Conceptual Vocabulary for Intelligent Tutoring Systems. Working paper available at:
  • Raymond, J. & Pilon, D. (1994). Software Tools for Computer-Aided Lecturing. IEEE Transactions on Education, 37 (1), 23-30.
  • Revesz, G. E. (1983). Introduction to Formal Languages. New York: McGraw-Hill.
  • Rist, T., Andre, E. & Muller, J. (1997). Adding Animated Presentation Agents to the Interface. In Proceedings of the IUI'97 Conference, Orlando, Florida: ACM Press, 79-86.
  • Szyperski, C. (1998). Component Software: Beyond Object-Oriented Programming, NY/Reading, MA: ACM Press/Addison-Wesley.
  • Vassileva, J. (1990). An Architecture and Methodology for Creating a Domain-Independent, Plan-Based Intelligent Tutoring System. Educational and Training Technology International, 27 (4), 386-397.
  • Valente, A., Russ, T., MacGregor, R. & Swartout, W. (1999). Building and (Re)Using an Ontology of Air Campaign Planning. IEEE Intelligent Systems, 14 (1), 27-36.
  • Wong, L.-H., Looi, C.-K. & Quek, H.-C. (1996). Design of an ITS for Inquiry Teaching. In Proceedings of The Third World Congress on Expert Systems, Seoul, Korea: Cognizant Communication Corporation, 1263-1270.