2nd Semester 2003/04: Interactive Visual Environments for DFA Induction

Instructors

Prof.Dr Pieter Adriaans

ECTS

6

Description

The purpose of this project of to create a visual environment that allows students to interact and experiment with language learning algorithms

It is well known that the class of languages recognized by a DFA (deterministic finite automaton) is equivalent to the class of regular languages. DFA's have the advantage of a very intuitive visual representation, which makes them very usful in a teaching context. Induction of regular languages using the DFA representation has been studied extensively over the past ten years. A well known basic algorithm is the so-called Evidence Based State Merging algorithm for the induction of DFA's on the basis of positive and negative examples. An extension based on the MDL (Minimum Description Length) principle can learn on the basis of positive examples alone (see the following powerpoint representation). In the lab session of the normal lnaguage learning course students students already make implementations of these algorithms. This project deals with the creation of an easy to use interactive environment in which the learning process is represented graphically on the computerscreen. The following functions should be supported:

1. Type in a number of strings
2. The following graphical stages should be visualized on the screen:
   Form MCA
   Form PTA
   Merging and backtrack operations
   Show final DFA
   
3. Generate new strings on the basic of the learned DFA
4. Store the results in a historical data base
5. The basic implementation will have a simple merging strategy and MDL as fintess criterion. Students should be able to write new plug-ins for these routines themselves.