A context-free grammar can be represented by a weighted finite-state
transducer. This representation can be used to efficiently compile that
grammar into a weighted finite-state automaton that accepts the strings
allowed by the grammar with the corresponding weights. The rules of a
context-free grammar are input. A finite-state automaton is generated
from the input rules. Strongly connected components of the finite-state
automaton are identified. An automaton is generated for each strongly
connected component. A topology that defines a number of states, and that
uses active ones of the non-terminal symbols of the context-free grammar
as the labels between those states, is defined. The topology is expanded
by replacing a transition, and its beginning and end states, with the
automaton that includes, as a state, the symbol used as the label on that
transition. The topology can be fully expanded or dynamically expanded as
required to recognize a particular input string.