Systems and methods for generating weighted finite-state automata representing grammars

• US 8,050,908 B2
• Filed: 06/06/2008
• Issued: 11/01/2011
• Est. Priority Date: 01/07/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Mohri, Mehryar, Nederhof, Mark-Jan
• Primary Examiner(s): SAINT CYR, LEONARD
• Application Number:
  US12/134,503
• Publication Number:
  US 20080243484A1
• Time in Patent Office: 1,243 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

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.

Claims

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.