Formal Grammars
A Journal of Mathematical Research on Formal and Natural Languages

Editor-in-chief: Carlos Martín-Vide
Special issues
Introduction
Volume 7(2004)
Volume 8(2005)
Editorial board
Aims and Scope
Subscription to the Hardcopy Edition
Submission procedure


Black Box and White Box Identification of Formal Languages Using Test Sets

MARC BEZEM, CHRISTIAN SLOPER, TORE LANGHOLM

Abstract

Moore's seminal paper can be taken as the starting point of Algorithmic Learning Theory. Moore studied the problem of unraveling the inner structure of a (minimum state) deterministic finite automaton (DFA) from its input-output behaviour. In this note we pursue Moore's line of research, studying conditions under which it is possible to compute a grammar and/or an automaton for a given language L from a language class C. It doesn't come as a surprise that such conditions must be quite strong. We improve on the algorithms in some cases where computing the grammar/automaton is possible. We correct some mistakes in the literature and come up with some new results, positive and negative, for (subclasses of) context-free languages.

Download:
PS file
PDF file
Copyright © 2004 GRLMC. All rights reserved.
Research Group on Mathematical Linguistics - Rovira i Virgili University
Webmaster