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 comprising:
generating a first finite-state automaton from a set of rules associated with a context-free grammar;
generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar;
generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and
modifying, via a processor, the third finite-state automaton by:
identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and
replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge.
2. The method of claim 1 , wherein each edge of the plurality of edges extends between an initial state and a final state, wherein the initial state and the final state are defined based on the topology.
3. The method of claim 2 , wherein the topology further identifies a constraint on the context-free grammar.
4. The method of claim 1 , wherein the context-free grammar has non-terminal symbols and terminal symbols.
5. A system comprising:
a processor; and
a computer-readable medium having instructions stored which, when executed by the processor, cause the processor to perform operations comprising:
generating a first finite-state automaton from a set of rules associated with a context-free grammar;
generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar;
generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and
modifying the third finite-state automaton by:
identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and
replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge.
6. The system of claim 5 , wherein each edge of the plurality of edges extends between an initial state and a final state, and wherein the initial state and the final state are defined based on the topology.
7. The system of claim 6 , wherein the topology further identifies a constraint on the context-free grammar.
8. The system of claim 5 , wherein the context-free grammar has non-terminal symbols and terminal symbols.
9. A non-transitory computer-readable storage medium having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising:
generating a first finite-state automaton from a set of rules associated with a context-free grammar;
generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar;
generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and
modifying the third finite-state automaton by:
identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and
replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge.
10. The non-transitory computer-readable storage medium of claim 9 , wherein each edge of the plurality of edges extends between an initial state and a final state, and wherein the initial state and the final state are defined based on the topology.
11. The non-transitory computer-readable storage medium of claim 10 , wherein the topology further identifies a constraint on the context-free grammar.
12. The non-transitory computer-readable storage medium of claim 9 , wherein the context-free grammar has non-terminal symbols and terminal symbols.