Systems and methods for regularly approximating context-free grammars through transformation
First Claim
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.
6 Assignments
0 Petitions
Accused Products
Abstract
Context-free grammars generally comprise a large number of rules, where each rule defines how a sting of symbols is generated from a different series of symbols. While techniques for creating finite-state automata from the rules of context-free grammars exist, these techniques require an input grammar to be strongly regular. Systems and methods that convert the rules of a context-free grammar into a strongly regular grammar include transforming each input rule into a set of output rules that approximate the input rule. The output rules are all right- or left-linear and are strongly regular. In various exemplary embodiments, the output rules are output in a specific format that specifies, for each rule, the left-hand non-terminal symbol, a single right-hand non-terminal symbol, and zero, one or more terminal symbols. If the input context-free grammar rule is weighted, the weight of that rule is distributed and assigned to the output rules.
83 Citations
30 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for generating a strongly regular grammar from a first grammar, comprising:
-
(a1) inputting a plurality of rules of the first grammar, each rule having a left-hand-side non-terminal symbol of the first grammar and at least one right-hand-side non-terminal symbol of the first grammar; (b1) identifying at least one strongly connected component of the first grammar; (c1) selecting one of the at least one identified strongly connected components; (d1) identifying non-terminal symbols of the selected strongly connected component; (e1) selecting one of the plurality of rules of the first grammar that has a left-hand-side non-terminal symbol that is one of the identified non-terminal symbols of the selected strongly connected component; (f1) selecting the left-hand-side non-terminal symbol of the selected grammar rule as a current left-hand-side non-terminal symbol; (g1) identifying a left-most non-terminal symbol on the right-hand side of the selected grammar rule that is one of the identified non-terminal symbols of the selected strongly connected component as a current right-hand-side non-terminal symbol; (h1) identifying any symbols of the right-hand side of the selected grammar rule located to the left of the left-most non-terminal symbol as current terminal symbols; and (i1) creating a first rule from the selected grammar rule for use in pattern recognition using the current left-hand-side symbol on the left-hand side of the first rule, any current 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 operation is an addition operator, the distributed weights must add together in the recombination to equal the weight of the first grammar rule. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A grammar rule transformation system that transforms an input grammar into a strongly regular grammar, comprising:
-
a left-hand symbol selecting circuit, routine or application that selects a non-terminal symbol to be used as a left-hand symbol of a new rule of the strongly regular grammar; a non-terminal symbol selecting circuit, routine or application that selects a right-hand-side non-terminal symbol of a rule of the input grammar to be used as a right-hand non-terminal symbol of the new rule of the strongly regular grammar; a terminal symbol selecting circuit, routine or application that selects zero, one or more right-hand-side terminal symbols of the rule of the input grammar to be used as zero, one or more right-hand terminal symbols of the new rule of the strongly regular grammar; a new rule generating circuit, routine or application that generates the new rule of the strongly regular grammar for use in pattern recognition based on the selected non-terminal symbol to be used as the left-hand symbol of a new rule of the strongly regular grammar, the selected non-terminal symbol to be used as the right-hand symbol of the new rule of the strongly regular grammar and the selected zero, one or more terminal symbols of the rule of the input grammar to be used as zero, one or more right-hand terminal symbols of the new rule of the strongly regular grammar; and a weighing circuit that equally distributes the weight of the first grammar rule to each of the rules in a portion of the set of strongly regular grammar rules if the first grammar rule has a weight 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 Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
Specification