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 method for converting a context-free grammar to a finite-state automaton representing the context-free grammar, the method comprising:
generating a first finite-state automaton from a set of rules associated with the context-free grammar;
generating, from the first finite-state automaton, at least one second finite-state automaton;
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 the at least one second finite-state automaton.
2. The method 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 method of claim 1 , wherein the topology identifies at least one constraint on the context-free grammar.
4. The method 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 context-free grammar.
5. The method of claim 1 , wherein generating the third finite-state automaton 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 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 method 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 method of claim 5 , wherein expanding the third finite-state automaton based on at least one of the at least one generated second finite-state automaton comprises replacing, 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 method of claim 7 , wherein expanding the third finite-state automaton is based on at least one of the at least one generated second finite-state automaton and the method further comprises repeating the replacing step for each edge of the expanded third finite-state automaton that is labeled with a non-terminal symbol of the context-free grammar.
9. The method of claim 7 , wherein replacing 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 comprises:
modifying that second finite-state automaton into a new automaton that accepts the non-terminal symbol with which that edge is labeled; and
substituting that edge with the new automaton.
10. The method of claim 9 , wherein modifying that second finite-state automaton into a new automaton that accepts the non-terminal with which that edge is labeled comprises modifying 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 method of claim 5 , wherein expanding the third finite-state automaton is based on at least one of the at least one generated second finite-state automaton, the method further comprising dynamically expanding 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 method of claim 11 , wherein dynamically expanding the third finite-state automaton based on an input string to be recognized by the third finite-state automaton comprises:
inputting the input string;
selecting a symbol of the input string;
determining, 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, replacing 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 method of claim 12 , wherein replacing the 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 comprises:
modifying that second finite-state automaton into a new automaton that accepts the selected symbol; and
substituting that edge with the new automaton.
14. The method of claim 13 , wherein modifying that second finite-state automaton into a new automaton that accepts the non-terminal with which that edge is labeled comprises modifying 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.
15. The method of claim 5 , wherein expanding the third finite-state automaton is based on at least one of the at least one generated second finite-state automaton and the method further comprises:
selecting an edge of the third finite-state automaton, the selected edge labeled with a non-terminal symbol of the context-free grammar;
selecting one of the at least one second finite-state automaton that corresponds to the non-terminal symbol with which the selected edge is labeled;
replacing the selected edge with the selected second finite-state automaton; and
repeating 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.
16. The method of claim 15 , wherein replacing the selected edge with the selected second finite-state automaton comprises:
modifying the selected second finite-state automaton into a new automaton that accepts the non-terminal symbol with which the selected edge is labeled; and
substituting that edge with the new automaton.
17. The method of claim 16 , wherein modifying the selected second finite-state automaton into a new automaton that accepts the non-terminal with which the selected edge is labeled comprises modifying the selected second finite-state automaton into a new automaton that accepts the non-terminal with which the selected edge is labeled based on a current status of the third finite-state transducer.
18. The method of claim 1 , wherein the context-free grammar has non-terminal symbols and terminal symbols.
19. The method of claim 1 , wherein each second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar.