INTRODUCTION
Automata theory is part of a typical computer science curriculum. Usually, it is studied in a course dealing with grammars, formal languages and possibly with compilers; a theoretical course with a mathematical flavour, that requires some mathematical maturity. Automata theory, even if it is an important part of the foundation of computer science and the theory of computation, may not meet the favours of computer science students, both because it is a mathematical subject and because the working examples are rather uninteresting if compared with the complexity of computer programs that they are asked to write. So students may miss the point and find the topic useless.
Mathematical subjects are often introduced to students using graphical representations, sometimes informally on blackboards, more often using standard diagrams and well established graphical methods, in order to improve their learning process. Although very useful to convey concepts, diagrams are static; even when they are used to better describe processes. Computer graphics provides ways to show dynamical processes and therefore it can be used to improve communication in a teaching task. In the case of automata, they can be introduced using the state diagram, which can be animated to show the computation process. Theorems on automata can be visualised as well; many of them provide a constructive method, that can be animated on the state diagram. Moreover the relation between automata and grammars can be explored: our environment Automata provides tools to define grammars, to check their types and to compute the relative automaton.
Neural networks have been more recently introduced into a computer science curriculum. It is a much less established field, but all the scholastic literature shows a similar attitude to the subject: at first the idea of formalising the structure of neural cells and their connections is introduced, then several different models of computation and learning methods are introduced (reef 4). There are packages that allows users to define and simulate networks, but none of them exploits graphics to show the process that take place on the net. We took this point of view, so that the structure of the net could be immediately perceived and learning algorithms could be seen in action.
1. AUTOMATA
For the theory of computation, we developed an environment where people can become familiar with different models of automata, can visualise their executions and make their connection to the theory of formal languages explicit. The implemented models are: Turing machines, deterministic finite automata, non deterministic finite automata and deterministic pushdown automata (ref. 3). A finite state automaton (FSA) is a mathematical model of systems which have a finite number of internal states and respond to external world just by changing their internal state. A finite state machine can be considered as a device that gives an indication whether or not an input sequence is accepted; it is therefore a language recogniser. Its reaction to an input, the external stimulus, can be deterministically determined by its state and current input or can be non deterministic. We distinguish therefore deterministic FSA from non deterministic ones; even though it is proved that the two models are equivalent since they recognize the same class of language. Finite state machines have been proven useful in different fields: computer science, first of all, where they are used in pattern matching, lexical analysis, word processing, compilers; but also in biology, electrical engineering and control theory.
This simple model can be enhanced by adding a device acting as store or memory: a stack. It is called pushdown automaton. This automaton accepts classes of languages that can not be recognized by finite state automata; therefore it is a more powerful device. In the case of pushdown automata deterministic or non deterministic behaviour makes a difference: the non deterministic pushdown automata are more powerful.
Finally a Turing machine, even if it is a very simple abstract computer, it is as powerful as any other computational model; therefore it serves as a base to introduce the concept of computable functions.
Structure of the environment Automata
The environment allows to define instances of a given model and to simulate its computation; it provides different formal representations of the computational device, such as regular expressions (REX) and grammars (ref.1). Automata theory includes a number of interesting algorithms, which are implemented in our environment, such as transforming nondeterministic FSA into deterministic ones, or minimizing an automaton, or converting a REX into finite automata. The algorithms are implemented in an interactive way, so that their execution is visualized.
Upon entering a grammar definition, with a grammar editor, users can choose to display the productions in Chomsky's or Greibach's normal form; they can check which kind of grammar it is, and if they are of type 3 or 2 (regular or context free) activate productions and see the word derivation tree. For regular grammars an algorithm is provided to construct the corresponding automaton interactively. For context free grammars, the automaton is built only if it is deterministic.
2. NEURALWORKS
Neural computing is another, rather new, programming paradigm; its basic concepts can be conveyed making use of dynamical simulations. The enviroment NeuralWorks provides tools for experimenting and modelling neural nets: it allows to design and simulate neural nets and to show the learning process (ref. 2, 3). It has a highly interactive graphical user interface: the net is defined giving its diagram, that shows the nodes and the connections, together with other information, according to user choice. After editing the network architecture, it is possible to associate it to a net model applying different simulation algoritms: the binary threshold neuron models with parallel and sequential updating rule, and the back propagation learning algorithm for multilayered networks of continuous neurons (ref. 4). The computation on the net can be visualized at regular steps or it can be performed in background for best performances. At present this application is transported under X-Window so that it will be available for different hardware platforms. The present net editor is much enhanced, in order to allow the addressing of part of the net as a whole. This feature allows to manage graphically also rather large nets, providing net iconizing and subnet managment facilities.
All applications have been developed in RMG [1], a graphic environment under UNIX [2] for workstation Hewlett-Packard 9000/300 series, and the code is written in Objective-C [3].
We would like to acknowledge the work of students, who implemented different modules as part of their thesis: P.Dell'Acqua (grammars), R.Fiammengo (regular expression), N.Nardini (pushdown automata), A.Paviglianiti (finite state automata), M.Scagliotti (Turing machines).