##
Efficient finite-state approximation of context free grammars

** Catherine Rood** (University of Cambridge)

This paper introduces a novel method for constructing finite--state
machines recognising context free (CF) grammars. The method utilizes
the idea of a * path* through a finite--state machine (FSM).
Certain paths form the basis for an * unfolding* process which is
applied to the LR(0) characteristic finite--state machine (CFSM)
corresponding to the grammar. The next section discusses the
approximation algorithm, including this unfolding process, in more
detail, and section 3 introduces the concept of an * unfolding
criterion*. Section 4 proves the soundness of the approximation
method, and its exactness to arbitrary, fixed recursive depths.
Section 5 presents initial computational figures resulting from an
implementation of the method. A variation of the method that is more
computationally feasible is discussed. The final section compares the
method with existing research on finite--state approximation of CF
grammars, and presents preliminary conclusions regarding the method.

PDF version (6 pages, 272k)