×

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

  • US 7,181,386 B2
  • Filed: 07/18/2002
  • Issued: 02/20/2007
  • Est. Priority Date: 11/15/2001
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for converting 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 method 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.

View all claims
  • 6 Assignments
Timeline View
Assignment View
    ×
    ×