×

Systems and methods for regularly approximating context-free grammars through transformation

  • US 7,289,948 B1
  • Filed: 07/22/2002
  • Issued: 10/30/2007
  • Est. Priority Date: 01/07/2002
  • Status: Active Grant
First Claim
Patent Images

1. A method for generating a set of strongly regular grammar rules from a first grammar rule, the first grammar rule having a plurality of non-terminal symbols and at least one terminal symbol, comprising:

  • (a) selecting a left-hand-side symbol of the first grammar rule as current left-hand-side symbol;

    (b) selecting a left-most non-terminal symbol of a right-hand side of the first grammar rule as a current right-hand-side non-terminal symbol;

    (c) identifying any terminal symbols of the right-hand side of the first grammar rule located to the left of the left-most non-terminal symbol; and

    (d) creating a first rule of the set of strongly regular grammar rules for use in pattern recognition using the current left-hand-side symbol on the left-hand side of the first rule, any identified terminal symbols as initial symbols on the right-hand side of the first rule, and the current right-hand-side non-terminal symbol as a last symbol on the right-hand side of the first rule;

    wherein if the first grammar rule has a weight, then the method further comprises equally distributing the weight of the first grammar rule to each of the rules in a portion of the set of strongly regular grammar rules such that the distribution of the weight, when recombined using a multiplicative operator over a semiring over which the weights are defined, equals the original weight of the first grammar rule, and wherein if the multiplicative operator is an addition operator, the distributed weights must add together in the recombination to equal the weight of the first grammar rule.

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