Systems and methods for generating weighted finite-state automata representing grammars
View Patent ↗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.
1. A system that converts a context-free grammar to a finite-state automaton representing the context-free grammar, the context-free grammar having non-terminal symbols and terminal symbols and having a set of rules, the system comprising:
a module that generates a first finite-state automaton from the set of rules;
a module that generates, from the first finite-state automaton, at least one second finite-state automaton, each second finite state automaton defining a delayed acceptor for a plurality of the non-terminal symbols of the context free grammar;
a module that receives a topology that defines an application of the context-free grammar;
a module that generates a third finite-state automaton that represents the received topology; and
a module that expands the third finite-state automaton based on at least one of the at least one generated second finite-state automaton.
2. The system of claim 1 , wherein the received topology defines at least one condition under which the context-free grammar is to be applied to an input string of symbols of the grammar.
3. The system of claim 1 , wherein the input topology identifies at least one constraint on the context-free grammar.
4. The system of claim 3 , wherein the at least one constraint defines at least one initial condition on the grammar under which the context-free grammar is to be applied to an input string of symbols of the grammar.
5. The system of claim 1 , wherein the module that generates the third finite-state automaton further:
defines at least one initial state based on the topology;
defines at least one final state based on the topology; and
defines a plurality of edges representing the active non-terminal symbols based on the topology, each edge labeled with one of the active non-terminal symbols and extending from at least one of an initial state and a final state of the third finite-state automaton.
6. The system of claim 5 , wherein each edge extends between one of the at least one initial state and one of the at least one final state.
7. The system of claim 5 , wherein the module that expands the third finite-state automaton based on at least one of the at least one generated second finite-state automaton further replaces, for each of the plurality of edges of the third finite-state automaton, that edge with one of the at least one second finite-state automaton based on the non-terminal symbol with which that edge is labeled.
8. The system of claim 7 , wherein the module that expands the third finite-state automaton based on at least one of the at least one generated second finite-state automaton further repeats the replacing step for each edge of the expanded third finite-state automaton that is labeled with a non-terminal symbol of the grammar.
9. The system of claim 7 , wherein the module that replaces one of the plurality of edges with the one of the at least one second finite-state automaton based on the non-terminal symbol with which that edge is labeled further:
modifies that second finite-state automaton into a new automaton that accepts the non-terminal symbol with which that edge is labeled; and
substitutes that edge with the new automaton.
10. The system of claim 9 , wherein the module that modifies that second finite-state automaton into a new automaton that accepts the non-terminal with which that edge is labeled further modifies that second finite-state automaton into a new automaton that accepts the non-terminal with which that edge is labeled based on a current status of the third finite-state transducer.
11. The system of claim 5 , wherein the module that expands the third finite-state automaton based on at least one of the at least one generated second finite-state automaton further dynamically expands the third finite-state automaton based on an input string to be recognized by the third finite-state automaton, the input string comprising a plurality of symbols of the context-free grammar.
12. The system of claim 11 , wherein the module that dynamically expands the third finite-state automaton based on an input string to be recognized by the third finite-state automaton further:
inputs the input string;
selects a symbol of the input string;
determines, based on the selected symbol, whether expanding of the third finite-state automaton is desirable; and
if expanding the third finite-state automaton is desirable, replaces an edge of the third finite-state automaton that is labeled with the selected symbol with one of the at least one second finite-state automaton that contains the selected symbol.
13. The system of claim 5 , wherein the module that expands the third finite-state automaton based on at least one of the at least one generated second finite-state automaton further:
selects an edge of the third finite-state automaton, the selected edge labeled with one of the non-terminal symbols of the context-free grammar;
selects one of the at least one second finite-state automaton that corresponds to the non-terminal symbol with which the selected edge is labeled;
replaces the selected edge with the selected second finite-state automaton; and
repeats the selecting steps and the replacing step until no edges labeled with one of the non-terminal symbols of the grammar remain in the third finite-state automaton.
14. The system of claim 1 , wherein the third finite-state automaton comprises:
at least one initial state defined by the topology;
at least one final state defined by the topology; and
a plurality of edges representing the active non-terminal symbols defined by the topology, each edge labeled with one of the active non-terminal symbols and extending from at least one of an initial state of the third finite-state automaton and a final state of the third finite-state automaton.
15. The system of claim 1 , wherein the module that generates the at least one second finite-state automaton further:
generates a dependency graph from the first finite-state automaton;
identifies at least one strongly connected component of the grammar based on the dependency graph; and
generates, from each of the at least one identified strongly connected component, one of the at least one second finite-state automaton.
16. The system of claim 15 , wherein generating the dependency graph from the first finite-state automaton comprises:
creating a dependency graph state for each non-terminal symbol of the input rules of the context-free grammar;
selecting one of the states of the first finite-state automaton;
selecting one of at least one edge extending from the selected state as a first selected edge, the first selected edge labeled with one of the non-terminal symbols and having a first end state to which it extends;
selecting one of at least one edge extending from the first end state as a second selected edge, the second selected edge labeled with one of the non-terminal symbols and having a second end state to which it extends;
determining if the second selected edge is labeled with a non-terminal symbol; and
if the second selected edge is labeled with a non-terminal symbol, creating an edge in the dependency graph extending from the dependency graph state for the non-terminal symbol with which the first selected edge is labeled to the dependency graph state for the non-terminal symbol with which the second selected edge is labeled.
17. A computer readable medium storing a computer program for controlling a computing device to convert a context-free grammar to a finite state automaton representing the context-free grammar, the context-free grammar having non-terminal symbols and terminal symbols and having a set of rules, the computer program including instructions comprising:
generating a first finite-state automaton from the set of rules;
generating, from the first finite-state automaton, at least one second finite-state automaton, each second finite state automaton defining a delayed acceptor for a plurality of the non-terminal symbols of the context free grammar;
receiving a topology that defines an application of the context-free grammar;
generating a third finite-state automaton that represents the received topology; and
expanding the third finite-state automaton based on at least one of the at least one generated second finite-state automaton.
18. The computer readable medium of claim 17 , wherein the received topology identifies at least one constraint on the context-free grammar.
19. The computer readable medium of claim 17 , wherein generating the third finite-state automaton further comprises:
defining at least one initial state based on the topology;
defining at least one final state based on the topology; and
defining a plurality of edges representing the active non-terminal symbols based on the topology, each edge labeled with one of the active non-terminal symbols and extending from at least one of an initial state and a final state of the third finite-state automaton.
20. The computer readable medium of claim 17 , wherein the third finite-state automaton comprises:
at least one initial state defined by the topology;
at least one final state defined by the topology; and
a plurality of edges representing the active non-terminal symbols defined by the topology, each edge labeled with one of the active non-terminal symbols and extending from at least one of an initial state of the third finite-state automaton and a final state of the third finite-state automaton.
21. The computer readable medium of claim 17 , wherein generating the at least one second finite-state automaton comprises:
generating a dependency graph from the first finite-state automaton;
identifying at least one strongly connected component of the grammar based on the dependency graph; and
generating, from each of the at least one identified strongly connected component, one of the at least one second finite-state automaton.