Web Based Instruction of Regular Expressions

Joe Klovance

Wendy Myrvold

University of Victoria

ABSTRACT

The course CSC 320 (Introduction to Theoretical Computer Science) is a mathematically intensive computer science course and is the only required undergraduate offering at the University of Victoria with the aim of rigorously proving that there are things which cannot be done on a computer. Understanding the computational models presented is critical to understanding the proofs in the course. Two barriers to this are the complexity of available texts, and the absence of a large collection of practice problems with solutions.

Our aim is to develop an interactive laboratory for the CSC 320 students based on www technology. Using the www has two major advantages: it permits easy access from labs or anywhere else with internet capabilities, and it is very easy to design a system allowing flexible navigation.

The initial phase of the project covers the material of the first 1/3 of the course: regular expressions, and deterministic finite automata. As a first step, we have designed a JAVA applet to test understanding of regular expressions. Students are asked to provide a regular expression for a given language. The JAVA applet checks the solution for correctness and provides detailed feedback for incorrect solutions.

The design of this system applies many of the constructive proofs presented early in the course. Further, it provides automated grading of questions which are difficult for teaching assistants to mark because there can be many correct solutions, and many other similar incorrect solutions to a given problem. Students will get immediate feedback and are encouraged to surf to a page presenting the background information when having difficulties with the problems. If extended to include all the material in the course, this system would provide an interactive alternative to the text or the basis for a distance learning course.