A Prolog Toolkit for Formal Languages and Automata

摘要

This paper describes the first version of P~b (read "P flat"), a collection of Prolog predicates that aims to provide a pedagogical implementation of concepts and algorithms taught in Formal Languages and Automata Theory (FLAT) courses. By "pedagogical implementation" we mean on the one hand that students should be able to easily map the implementation to the mathematical definitions given in lectures, and on the other hand that the toolkit should provide a library for students to implement further concepts and algorithms. In both cases the goal is to make students more confident in defining and manipulating the various kinds of languages and automata at a level beyond the one provided by visual simulators of automata. As such, P~b is not intended to replace but rather complement existing graphical tools. We believe the declarative, non-deterministic, and interactive nature of Prolog helps in building an executable specification of FLAT concepts and definitions that can be actively extended and explored by students, in order to achieve the stated goal.