JCS&T Vol. 4 No.

2 August 2004

Invited Paper:

Learning by Generation in Computer Science Education

Andreas Kerren
Institute of Computer Graphics and Algorithms, Vienna University of Technology
Favoritenstraße 9-11, A-1040 Vienna, Austria
e-mail: [email protected]

ABSTRACT e. g., a control for learning targets whereas other ele-

ments, like interfaces to knowledge databases, have a
The use of generic and generative methods for the more subject-related character. The system InterTalk of
development and application of interactive educational Diehl and Ohlmann realizes such a generic concept. It is
software is a relatively unexplored area in industry described at the web site [11] in more detail.
and education. Advantages of generic and generative In addition to reduction of development costs and soft-
techniques are, among other things, the high degree ware reusability, generative methods can be used for real-
of reusability of systems parts and the reduction of izing new learning models. Such a learning model, called
development costs. Furthermore, generative methods “levels of exploration”, is discussed by Diehl and Kerren
can be used for the development or realization of novel in the conference paper [8] and clarified with topics in
learning models. In this paper, we discuss such a compiler construction and formal languages. Visualiza-
learning model that propagates a new way of explorative tions and animations of computational models, e. g., fi-
learning in computer science education with the help nite automata or abstract machines (see [24]) are consid-
of generators. A realization of this model represents ered which can be integrated in ES for compiler construc-
the educational software G ANI FA on the theory of tion. The discussed learning model could also be used for
generating finite automata from regular expressions. other process-oriented application areas, like electrical
In addition to the educational system’s description, we engineering or physics. Important is the descriptiveness
present an evaluation of this system. of these processes by specifications. It divides explo-
rative learning [6] into four different levels. The degree
Keywords: Finite automata, generation, explorative of learner exploration is relatively limited in the first both
learning, visualization, animation, evaluation levels: they describe a static approach (level 1) on the one
hand respectively an interactive approach (level 2) on the
other.
1. INTRODUCTION In the static approach, the execution of an instance of
a computational model is animated for a given, fixed in-
During the past years, the development of interactive,
put. This approach has a strong behavioristic character-
multimedial learning software has become more and
istic (see [23]). The knowledge transfer of the working
more relevant in industry and education. In Germany,
of a special instance is in the foreground and the pas-
research funds of several millions EUR were supplied
sive learner has only a low influence on the kind of the
for the research and development of new media in educa-
presented information. He/she has merely the control
tion. However, generic and generative approaches for the
on when the animation is started or how fast the anima-
implementation and application of such educational soft-
tion runs. An example for an implementation of this ap-
ware (ES) are neither in the center of actual research in-
proach is the A DL A-system of Braune et al. [5]: an ES on
terests nor have they been realized frequently. Important
the theory of lexical analysis of programming languages
advantages of generic and generative techniques are the
with the help of finite automata.
high level of software reusability and the reduction of de-
In the interactive approach, an user-defined input is
velopment costs (see [18, 20]). For example, ES mostly
possible. This approach supports the learner to exam-
supports the same kind of exercises. This is a well-suited
ine computational models with own examples. But, the
starting-point for using generative tools and techniques
visualized instance of the computational model is—as in
which focus on the automated development of software
the static approach—fixed and cannot be changed. The
from formal specifications. By means of them, exercises
A DS A-system [16, 17] for the animation of the semanti-
can be generated from specifications. It is no law that
cal analysis of programming languages is an example for
such a specification has to declare only from teachers.
this interactive approach.
Also the learner can use this possibility, see the next Sec-
tion 2 for details. We will concentrate on such generative So far, generators for producing animations of in-
methods in the rest of the paper1 . stances of computational models from specifications
have been ignored. In the next section, we discuss how
Different from this, generic ES is developed for a
generative methods can facilitate explorative learning
whole content area. Following, instances are built for
with the help of both higher levels of exploration. Then, a
special learning units. A common part of ES could be,
generative ES system is presented. Its learning efficiency
1 This paper is a slightly modified and extended version of [19] that is analyzed on the basis of an evaluation with more than
was presented at the ACM ITiCSE ’04 Conference in Leeds, UK. 100 participants.

84
JCS&T Vol. 4 No. 2 August 2004

2. LEARNING BY GENERATION generating computational models on the other hand. Sec-

tion 3 describes an ES system that realizes this second-
Figure 1 shows a coarse overview of a potentially
order generative approach. In the context of learning,
HTML-based ES which uses generative techniques.
we combine these two generative approaches to the term
The HTML-document covers the learning content of a
“learning by generation”.
process-oriented topic, i. e., it contains definitions, de-
scriptions, images, simple examples, etc. Additionally,
the learner can formulate a specification of a process de-
scribed in the HTML-document. This specification is
transferred to a generator embedded into the ES. The
generator produces a didactically wise representation of
the specified process, e. g., a visualization (including an-
imations) or an auralization. The ES offers an—possibly
generated—interface to this representation that is used by
the learner for input, interaction or control purposes.

Figure 2: Use of the second-order generative approach

Our second-order generative approach leads to an

analogy with the so-called “microworlds” metaphor.
This term means a tiny world inside which a learner can
explore alternatives, test hypotheses, manipulate con-
stituent parts, and discover facts that are true about that
world, see for example [23]. Thus, microworlds are sim-
Figure 1: Use of generative methods for developing ES ilar to the well-known simulations which can be found in
ES on physics or electrical engineering. A microworld
In essence, the last paragraph discussed the generative differs from a simulation in that it can be considered as a
approach of the third level [8]. Beside the pure knowl- second-order simulation that supports the own construc-
edge transfer, the understanding and the interpretation tion or modification of models instead of a pure monitor-
of the learning content should be encouraged. Informa- ing of a model. Blumstengel [2] states that microworlds
tion is not structured by a teacher but learners have to (and simulations too) often promote active and explo-
explore and to order their own information. This ap- rative learning and act motivating if the ES has a good
proach (called “first-order generative approach”) enables didactical design.
learners to formulate new hypotheses and validate them Furthermore, learning by generation is closely re-
by changing specifications or user inputs. The G ANI - lated with the constructivist view of learning. The term
MAM -system [10] is an example for an implementation
“constructivism” refers to the idea that learners con-
of the first-order generative approach. It is about a web- struct knowledge for themselves as he or she learns.
based generator for interactive animations of abstract ma- Each learner individually and socially constructs mean-
chines. The learner can enter a specification of an ab- ing. Therefore, knowledge cannot be transferred in a tra-
stract machine as instance of a given machine model. A ditional way, e. g., by instruction. The learner has to inte-
generator produces a visualization of the specified ab- grate the knowledge into his/her individual mental struc-
stract machine in the shape of an interactive JAVA applet. ture and existing knowledge constructs. Consequently,
This generated machine can interpret machine instruc- moderate constructivism attaches great importance to the
tions written by hand or automatically translated from a creation and design of stimulating learning environments
high level programming language. The learner can find that give the learner the possibility to generate individual
out much about the computational model, but nothing knowledge constructs (cp. [15, 23, 2]).
about its generation process.
This disadvantage is avoided by the generative ap-
proach of the fourth level (called “second-order gener- 3. TEST CASE: GANIFA
ative approach”). Here, we can check hypotheses about
the generation process itself because the generator is rep- In context of the G ANIMAL project2 [13], we have de-
resented within the ES, e. g., in form of an animation, see signed a development environment for the realization of
Figure 2. Such a system supports the learner to better the fourth level of exploration. The resulting ES system,
understand the computational model (or any process in called G ANI FA, is an electronic, HTML-based textbook
general) but also the working of generators which pro- on the theory of finite automata and their generation from
duce instances of such models. This is one of the most regular expressions [9]. G ANI FA can be locally used as
important insights on the teaching of compiler construc- well as via the Internet [12, 4].
tion. According to this, learners should really understand 2 This research has been partially supported by the German Research

mathematical basics on the one hand and coherences at Council (DFG) under grant number WI 576/8-1 and WI 576/8-3.

85
JCS&T Vol. 4 No. 2 August 2004

(a) Textbook: explanations to a minimization algorithm

(b) Animation of the generation of a NFA from a RE (a|b)∗

(c) Animation of the minimization algorithm based on a DFA that was generated from the RE a|b|c∗

Figure 3: Screenshots of the G ANI FA system

86
JCS&T Vol. 4 No. 2 August 2004

System Description or a regular expression respectively an input word to the

applet directly. Based on these functionalities, G ANI FA
The textbook introduces into the theory of finite au-
supports the second-order generative approach.
tomata. Particularly, it gives an overview of general for-
mal languages, regular languages and expressions. After-
wards, transition diagrams, non-deterministic and deter- Evaluation
ministic finite automata are described in more detail. The An evaluation of new ES should give information about
system shows formal definitions in a separate browser its usability and effectiveness. Unfortunately, most of
window if the learner chooses the corresponding hyper- new ES systems are not evaluated adequately. One rea-
links in the textbook. son could be that there is a risk to get bad results. Conse-
Advanced techniques for software generation as used quences are a bad usability, inconsistent design or im-
in compiler construction have been applied to the auto- practical preparation of learning contents. The accep-
matic generation of animations contained in the learning tance and effectiveness of G ANI FA were proved by a
system, i. e., in the form of a customizable JAVA applet. summative evaluation (see e. g. [2]) based on learning
It is possible to specify any finite automata with the help experiments with more than 100 test persons. Aim of
of regular expressions and to animate the respective gen- this evaluation is to prove that persons learning with the
eration process. Figure 3 shows three different screen- generative ES system G ANI FA have an equal or a better
shots: on Subfigure 3(a), one page of the electronic text- learning performance than persons learning with other
book is displayed. It contains explanations to the theory teaching methods. We used inferential statistics (t-test
on minimizing finite automata as well as to an appro- resp. analysis of variance (ANOVA)) to execute the anal-
priate algorithm. The minimization is the last phase of ysis.
the whole generation process. Via hyperlink, the learner
can change to another page containing a form to enter a Test Design: At first, we performed an usability
regular expression. First, the generator produces a non- test together with some students to detect mistakes of the
deterministic finite automaton (NFA) from a regular ex- electronic textbook. Typos, dead hyperlinks, runtime er-
pression, e.g. (a|b)∗ . This generation process is repre- rors of the JAVA applet, etc. lead to a painful system
sented by an animation. Subfigure 3(b) illustrates three appliance and increase the risk of a negative evaluation
steps of the generation of a NFA. After that, the user result from the first.
could enter an input word to watch the acceptance be- As test persons (TP) we chose 118 students of a com-
havior of the generated automaton or he/she could com- puter science foundation course at the Saarland Univer-
pletely skip over all intermediate phases of the generation sity in Germany. The evaluation was not announced, i. e.,
(see below) to watch the minimization phase only. An the students could not agree to participate. In this way,
example animation of the minimization algorithm on the we could eliminate registrations of test persons who have
basis of the regular expression a|b|c∗ is shown by Sub- a positive/negative preference for interactive, multime-
figure 3(c). Each generation phase can be animated with dial ES. They were informed at the beginning of the lec-
the help of the G ANI FA system: ture and evenly divided into four groups. Each group was
escorted to a separate room. As schematically shown in
1. Generation of a non-deterministic finite automaton Figure 4, these four learner groups studied the theory of
(NFA) from a regular expression (RE) [24]. generating finite automata each with the help of differ-
2. Removal of ε-transitions of a NFA [22, 24]. ent methods: classical instruction, text book, and two
ES systems with (G ANI FA) and without (A DL A) gen-
3. Transformation of a deterministic finite automaton erative part. All groups had a time frame of 35 minutes.
(DFA) from a NFA without ε-transitions [22, 24]. We had to take care of identical presentation of learn-
ing content between the groups. Following the learning
4. Minimization of a deterministic finite automaton
phase, an exercise with nine knowledge and ten trans-
(minDFA) [14].
fer questions was performed. Knowledge questions ask
(5.) The G ANI FA-applet can visualize the computation for the reproduction of learning content described by the
of each generated automaton on an user-defined in- learning method. Additionally, transfer questions ask for
put word. a deeper understanding of the content. Finally, all test
persons should complete questionnaires with regard to
The applet draws all generated automata as transition personal statements and teaching aids (learning meth-
diagrams using a special graph layout algorithm in order ods). They are based on 11-ary rating scales with nu-
to preserve the mental map [21], see the paper of Diehl meric markers and on so-called “open questions”: test
et al. [7] for details. In addition, it is possible to visual- persons could formulate their answers in written form.
ize the acceptance behavior of generated automata for an Note that all participants were informed about their re-
input word entered by the learner (see Item 5 of the enu- sults on a special web page. For this purpose, they could
meration). The G ANI FA-applet is customizable through leave their matriculation number on the questionnaire.
a large set of parameters, and it is easy to integrate the ap-
plet into existing web pages. So, it is possible to visualize Results: In a first step, we performed a descriptive
only a range of algorithms and to pass a finite automaton analysis of our data. Through summation of all achieved

87
JCS&T Vol. 4 No. 2 August 2004

118
118Test
TestPersons
Persons(TP)
(TP)

Learning with Software

29
29TP 30
30TP 30
30TP 29
29TP

“Traditional“ Learning
TP TP TP TP

AdlA
AdlA GaniFA
GaniFA Text
Text Lecture
Lecture
Length: approx. 35 min Length: approx. 35 min

• 19 Knowledge Questions
Length: approx. 25 min Exercise
Exercise • 10 Transfer Questions

• Teaching Aids Benchmark

Length: approx. 15 min Questionnaire
Questionnaire • Personal Statements

Figure 4: Test design of our evaluation

Knowledge Questions Transfer Questions

7 11
10
6
9
5 8
AdlA AdlA
7
K-Index

T-Index

4 GaniFA GaniFA
6
3 Text 5 Text
4
2 Lecture 3 Lecture
1
2
5,75 5,57 6,00 5,02 1 6,83 7,27 7,00 5,93
0 0
Test Groups Test Groups

Figure 5: Histograms of means of summative performance indices for the knowledge (maximal score: 7) and transfer
questions (maximal score: 13)

6,2 6,0
K-Index: Estimated Mean
K-Index: Estimated Mean

6,0 5,8

5,8
AdlA 5,6 AdlA
5,6
GaniFA GaniFA
5,4
5,4 Text Text
Lecture 5,2 Lecture
5,2

5,0
5,0

4,8 4,8

S15 S13

Figure 6: Estimated performance differences between teaching methods for the knowledge questions with involvement
of the control variables S15 and S13

88
JCS&T Vol. 4 No. 2 August 2004

scores for the exercise answers, we obtain the statisti- formal”. There was a further problem if students tried to
cal values of the sample, shown at Figure 5. The stan- enter their own regular expressions: regular expressions
dard deviations are represented as error bars. In case had to be completely set in brackets. This did not meet
of the knowledge questions (K-Index), the performance the established standard in this area. We could not cor-
mean PM of the text group is the highest one (PM = rect the non-intuitive input of them early enough.
6, 00). Otherwise, the highest performance mean for the
transfer questions (T-Index) goes to the G ANI FA group
Web Access Statistics
(PM = 7, 27). This result would confirm our assump-
tion that a conventional text book is a better choice to We have analyzed the web access to the electronic text-
learn basic knowledge than one of the both ES systems if book G ANI FA on the basis of the web server’s log files.
a suitable statistical test model would have a significant This was done within a time period of 27 days. In this
result. In contrast, the both ES systems would have ad- period of time, we could identify web accesses to at least
vantages in the consolidation and deeper understanding one web page of the textbook from 479 IP addresses (no
of the learned knowledge. robots). Note that all accesses from the same IP address
An one-factorial analysis of variance that scans the were counted several times if they did not occur within
random differences of the learning efficiency between one hour. 44.9 % of them were accesses to at least three
our four groups adduces no significant results neither at web pages of the textbook, i.e., we had an average value
the knowledge questions nor at the transfer questions. of approximately 8 user accesses per day. More than
Also, we could not discover any difference computing 50 % of these users accessed to at least one web page
the effect value [3]. In consequence, we tried to improve that contained the embedded JAVA applet. But we could
the precision of our analysis with the help of a covariance not ascertain how many users had really run the applet.
analysis. With involvement of two control variables S15
“computer science course at school as intensive/basic
course, voluntary study group, or no course” and S13 4. CONCLUSION
“mathematics in school as intensive/basic course”, we In this paper, an approach for explorative learning with
obtained with S15 a significant performance difference generative methods was presented. Learning by gener-
at the knowledge questions in favor of the text group (er- ation has a constructivist orientation and supports self-
ror probability: 4,1 %). The G ANI FA group and the organized and self-controlled learning. Our educational
text group had nearly the same performance with con- software G ANI FA is a realization of this approach and
trol of S13. For both control variables, the G ANI FA was developed in context of the G ANIMAL project. We
group achieved a performance improvement in compar- discussed the system in more detail as well as an evalua-
ison with the A DL A and the lecture group (error proba- tion of the system with more than 100 participants. The
bility: 4,7 %), cp. Figure 6. So, we have a solid base results of the following statistical analysis prove that the
for further optimizations and development of the G ANI - learning efficiency of G ANI FA is higher than the one of
FA system and of the discussed second-order generative classical instruction and nearly as good as the textbook’s.
approach3 . G ANI FA was observed as learning aid very positively.
A critical view on the test design lets infer that a part of The most participants would like to use G ANI FA as lec-
the knowledge questions was chosen too simple because ture supplement. Admittedly, the test design itself can
of the very good average performance results in this cat- be critically regarded because of the necessary improve-
egory. Is is possible that some effects could fail to appear ments with respect to the influence of user interaction at
for this reason. Future evaluations should include a pre- the educational software.
test to check the previous knowledge of the participants.
Furthermore, it is probably that the short time frame of
the evaluation was not sufficient to discover all advan- 5. ACKNOWLEDGEMENTS
tages and interactive possibilities of the G ANI FA system.
I would like to thank Stephan Diehl, Carsten Görg,
In general, this could be a drawback of our (widely-used)
Torsten Weller, Julia Kneer, Christoph Glasmacher, and
test design, cp. the statements of Baumgartner [1].
all other people involved in the G ANIMAL project.
The answers of the open questions show that the elec-
tronic textbook G ANI FA is well-convenient as meaning-
ful supplement of traditional learning/teaching methods 6. REFERENCES
because of the interactive animations, clarity, and better
motivation. The students liked the generated animations [1] P. Baumgartner. Evaluation of Media-based Learn-
of G ANI FA and esteemed to work indepedendly and to ing (in German). In M. Kindt, editor, Projektevalu-
use all possibilities of our generated animations. This ation in der Lehre – Multimedia an Hochschulen
good opinion holds also for graphics, didactical design zeigt Profil(e), pages 61–97. Waxmann, Münster,
and formal definitions in a separate definition window. 1999.
Some students disliked the form of the definitions: “too
[2] A. Blumstengel. Development of Hypermedial
3A more detailed description of the realization and analysis of this Learning Systems (in German). Wissenschaftlicher
evaluation is contained in the author’s PhD thesis [18]. Verlag Berlin, WVB, 1998.

89
JCS&T Vol. 4 No. 2 August 2004

[3] J. Bortz. Statistics for Social Scientists (in Ger- [14] J. Hopcroft and J. Ullman. Introduction to Au-
man). Springer, Berlin, Heidelberg, 5. edition, tomata Theory, Languages and Computation.
1999. Addison-Wesley, 1979.

[4] B. Braune, S. Diehl, A. Kerren, T. Weller, and R. [15] D. H. Jonassen, T. Mayes, and R. McAleese. A
Wilhelm. Generating Finite Automata – An Interac- Manifesto for a Constructivist Approach to Uses of
tive Online Textbook, 2002. URL: http://www. Technology in Higher Education. In T. M. Duffy,
cs.uni-sb.de/GANIMAL/GANIFA. J. Lowyck, and D. H. Jonassen, editors, Designing
Environments for Constructive Learning, volume
[5] B. Braune, S. Diehl, A. Kerren, and R. Wilhelm, 105 of NATO ASI, Series F, Computer and System
Animation of the Generation and Computation of Sciences, pages 231–247. Springer, Berlin, Heidel-
Finite Automata for Learning Software. In Au- berg, New York, London, 1993.
tomata Implementation, Proceedings of the 4th In-
ternational Workshop on Implementing Automata [16] A. Kerren. Animation of the Semantical Analysis
(WIA ’99), volume 2214 of Lecture Notes on Com- (in German). In Proceedings of the 8th GI Confer-
puter Science, LNCS, pages 39–47, Potsdam, 1999. ence on Informatics and School (INFOS ’99), In-
Springer. formatik aktuell, pages 108–120. Springer, 1999.

[6] J. S. Bruner. The Act of Discovery. Harvard Edu- [17] A. Kerren. Visualization and Animation of the Se-
cational Review, 31:21–32, 1961. mantical Analysis of Programs (in German). Infor-
matica Didactica – Journal on Didactical Basics in
[7] S. Diehl, C. Görg, and A. Kerren. Preserving the Informatics, 1(1), 2000.
Mental Map using Foresighted Layout. In Proceed-
ings of Joint Eurographics – IEEE TCVG Sym- [18] A. Kerren. Generation of Interactive Animations
posium on Visualization (VisSym ’01), Eurograph- for Compiler Design (in German). PhD thesis,
ics, pages 175–184, Ascona, Swizerland, 2001. Saarland University, Saarbrücken, Germany, 2002.
Springer. Shaker Verlag, Aachen, ISBN 3-8322-0899-2.

[8] S. Diehl and A. Kerren. Levels of Exploration. [19] A. Kerren. Generation as Method for Explorative
In Proceedings of the 32nd ACM Technical Sym- Learning in Computer Science Education. In Pro-
posium on Computer Science Education (SIGCSE ceedings of the 9th Annual Conference on Innova-
’01), pages 60–64, Charlotte, NC, USA, 2001. tion and Technology in Computer Science Educa-
ACM. tion (ITiCSE ’04), pages 77–81, Leeds, UK, 2004.
ACM Press.
[9] S. Diehl, A. Kerren, and T. Weller. Visual Ex-
ploration of Generation Algorithms for Finite Au- [20] A. Kerren, R. Wilhelm, and S. Diehl. MALL
tomata. In Implementation and Application of Au- – Final Report (in German), June 2000.
tomata, volume 2088 of Lecture Notes on Com- URL: http://www.cs.uni-sb.de/RW/
puter Science, LNCS, pages 327–328. Springer, projects/mall/.
2001.
[21] K. Misue, P. Eades, W. Lai, and K. Sugiyama. Lay-
[10] S. Diehl and T. Kunze. Visualizing Principles of out Adjustment and the Mental Map. Journal of
Abstract Machines by Generating Interactive An- Visual Languages and Computing, 6(2):183–210,
imations. Future Generation Computer Systems, 1995.
16(7), 2000. Elsevier.
[22] M. Rabin and D. Scott. Finite Automata and their
[11] S. Diehl and M. Ohlmann. InterTalk, 2002. URL: Decision Problems. IBM J. Res. Dev, 3/2:115–125,
http://www.cs.uni-sb.de/∼diehl/ 1959.
InterTalk/.
[23] R. Schulmeister. Basics of Hypermedial Learning
[12] GaniFA. Download Page, 2002. URL: Systems (in German). Addison-Wesley, Bonn,
http://www.cs.uni-sb.de/GANIMAL/ 1996. English version accessible under URL:
download.html. http://www.izhd.uni-hamburg.de/
paginae/Book/Frames/Start FRAME.
[13] Ganimal. Project Homepage, 2002. URL: http: html.
//www.cs.uni-sb.de/GANIMAL.
[24] R. Wilhelm and D. Maurer. Compiler Design: The-
ory, Construction, Generation. Addison-Wesley, 2.
edition, 1996.

90