Method and apparatus for creating speech recognition grammars constrained by counter examples

Claim 1

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator means for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating from said initial grammar rules and said list of counter example sentences a revised grammar, wherein said counter example sentences are illegal in said revised grammar.

Claim 2

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator means for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating from said initial grammar rules and said list of counter example sentences a revised grammar, wherein said counter example sentences are illegal in said revised grammar.

Claim 4

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating therefrom a revised grammar wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar revisor means comprises: counter-example remover means for removing said counter-example sentences from said list of possible sentences and outputting a pruned list; and a grammar generator means, receiving said pruned list and outputting said revised grammar, wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar generator means comprises: means for generating a unique non-terminal for each word in said pruned list; means for computing a base optimization criterion value based on properties of words in said pruned list for said initial grammar; means for concatenating a pair of non-terminals and computing a first resultant optimization criterion value; means for merging said pair of non-terminals and computing the second resultant value of said optimization criterion; and means for adding a new grammar rule to said initial grammar in accordance with an optimal of said first and second optimization criterion values.

Claim 5

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating therefrom a revised grammar wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar revisor means comprises: counter-example remover means for removing said counter-example sentences from said list of possible sentences and outputting a pruned list; and a grammar generator means, receiving said pruned list and outputting said revised grammar, wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar generator means comprises: means for generating a unique non-terminal for each word in said pruned list; means for computing a base optimization criterion value based on properties of words in said pruned list for said initial grammar; means for concatenating a pair of non-terminals and computing a first resultant optimization criterion value; means for merging said pair of non-terminals and computing the second resultant value of said optimization criterion; and means for adding a new grammar rule to said initial grammar in accordance with an optimal of said first and second optimization criterion values.

Claim 8

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating therefrom a revised grammar wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar revisor means comprises: counter-example remover means for removing said counter-example sentences from said list of possible sentences and outputting a pruned list; and a grammar generator means, receiving said pruned list and outputting said revised grammar, wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar generator means comprises: means for generating a unique non-terminal for each word in said pruned list; means for computing a base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; means for concatenating a pair of said non-terminals and computing a resultant value of said optimization criterion and for adding a new rule for said concatenated pair to said initial grammar if said value of criterion is more optimal than said base value of said optimization criterion; and means for merging said pair of said non-terminals and computing a resultant value of said criterion and for adding a new rule for said merged pair to said initial grammar if said resultant value of optimization criterion is more optimal than said base value of criterion.

Claim 9

A system for creating grammars for a speech recognition application, comprising: speech grammar repository means for receiving an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; sentence generator means for generating a list of possible sentences according to said initial grammar rules; counter-example generator for analyzing said list of possible sentences and generating a list of counter example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and a grammar revisor means, receiving said initial grammar rules and said list of counter example sentences, for generating therefrom a revised grammar wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar revisor means comprises: counter-example remover means for removing said counter-example sentences from said list of possible sentences and outputting a pruned list; and a grammar generator means, receiving said pruned list and outputting said revised grammar, wherein said counter example sentences are illegal for said speech recognition application, wherein said grammar generator means comprises: means for generating a unique non-terminal for each word in said pruned list; means for computing a base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; means for concatenating a pair of said non-terminals and computing a resultant value of said optimization criterion and for adding a new rule for said concatenated pair to said initial grammar if said value of criterion is more optimal than said base value of said optimization criterion; and means for merging said pair of said non-terminals and computing a resultant value of said criterion and for adding a new rule for said merged pair to said initial grammar if said resultant value of optimization criterion is more optimal than said base value of criterion.

Claim 11

A system for creating grammars for a speech recognition application as recited in 7 wherein said initial grammar is expressed in Backus-Naur Form (BNF) notation.

Claim 12

A system for creating grammars for a speech recognition application as recited in 7 wherein said initial grammar is expressed in Backus-Naur Form (BNF) notation.

Claim 13

A method for modifying grammars for a speech recognition application, comprising steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and generating from said initial grammar rules and said counter-example sentences a revised grammar wherein said counter example sentences are illegal.

Claim 14

A method for modifying grammars for a speech recognition application, comprising steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; and generating from said initial grammar rules and said counter-example sentences a revised grammar wherein said counter example sentences are illegal.

Claim 16

A method for modifying grammars for a speech recognition application comprising the steps: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; removing said counter-example sentences from said list of possible sentences and outputting a pruned list; revising said initial grammar with said pruned list and outputting a revised grammar wherein said counter example sentences are illegal; generating a unique non-terminal for each word in said pruned list; computing the base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; concatenating a pair of said non-terminals and computing a first resultant value of said optimization criterion; merging said pair of non-terminals and computing a second resultant value of said optimization criterion; and adding a new grammar rule to said initial grammar in accordance with an optimal of said first and second resultant value.

Claim 17

A method for modifying grammars for a speech recognition application comprising the steps: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; removing said counter-example sentences from said list of possible sentences and outputting a pruned list; revising said initial grammar with said pruned list and outputting a revised grammar wherein said counter example sentences are illegal; generating a unique non-terminal for each word in said pruned list; computing the base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; concatenating a pair of said non-terminals and computing a first resultant value of said optimization criterion; merging said pair of non-terminals and computing a second resultant value of said optimization criterion; and adding a new grammar rule to said initial grammar in accordance with an optimal of said first and second resultant value.

Claim 20

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; removing said counter-example sentences from said list of possible sentences and outputting a pruned list; revising said initial grammar with said pruned list and outputting a revised grammar wherein said counter example sentences are illegal; generating a unique non-terminal for each word in said pruned list; computing a base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; concatenating a pair of said non-terminals and computing a resultant value of said criterion and adding a new rule for said concatenated pair to said initial grammar if said resultant value of optimization criterion is more optimal than said base value of optimization criterion; and merging said pair of said non-terminals and computing a resultant value of said optimization criterion and adding a new rule for said merged pair to said initial grammar if said resultant value of said optimization criterion is more optimal than said base value of optimization criterion.

Claim 21

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; removing said counter-example sentences from said list of possible sentences and outputting a pruned list; revising said initial grammar with said pruned list and outputting a revised grammar wherein said counter example sentences are illegal; generating a unique non-terminal for each word in said pruned list; computing a base value of an optimization criterion based on properties of the words in said pruned list for said initial grammar; concatenating a pair of said non-terminals and computing a resultant value of said criterion and adding a new rule for said concatenated pair to said initial grammar if said resultant value of optimization criterion is more optimal than said base value of optimization criterion; and merging said pair of said non-terminals and computing a resultant value of said optimization criterion and adding a new rule for said merged pair to said initial grammar if said resultant value of said optimization criterion is more optimal than said base value of optimization criterion.

Claim 24

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; generating a parse tree comprising a plurality of non-terminals for each of said sentences in said list of counter-example sentences; adding a new non-terminal for each non-terminal in said parse tree which generates each phrase that said non-terminal generates but excludes phrases in said list of counter-example sentences; and modifying a START non-terminal in said parse tree wherein said START non-terminal excludes sentences in said list of counter-example sentences.

Claim 25

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; generating a parse tree comprising a plurality of non-terminals for each of said sentences in said list of counter-example sentences; adding a new non-terminal for each non-terminal in said parse tree which generates each phrase that said non-terminal generates but excludes phrases in said list of counter-example sentences; and modifying a START non-terminal in said parse tree wherein said START non-terminal excludes sentences in said list of counter-example sentences.

Claim 26

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; generating a parse tree comprising a plurality of non-terminals <N> for each of said sentences in said list of counter-example sentences; for each non-terminal <N > in said parse tree except a <<Start>> symbol: creating a new rule <N'> such that <N'> generates all phrases generated by <N> except any phrases which are in said list of counter-example sentences; creating a new rule <No> such that <No> generates only phrases which are in said list of counter-example sentences and generated by <N>; and modifying a rule containing said <<START>> symbol in said parse tree such that said rule containing said <<START>> symbol ceases to generate said sentences in said list of counter-example sentences.

Claim 27

A method for modifying grammars for a speech recognition application comprising the steps of: creating an initial grammar for a speech recognition system and outputting a set of initial grammar rules for said initial grammar; generating a list of possible sentences according to said initial grammar rules; generating a list of counter-example sentences comprising sentences which are legal within said initial grammar rules but which are inapplicable for said speech recognition application; generating from said initial grammar rules a revised grammar wherein said counter example sentences are illegal; generating a parse tree comprising a plurality of non-terminals <N> for each of said sentences in said list of counter-example sentences; for each non-terminal <N > in said parse tree except a <<Start>> symbol: creating a new rule <N'> such that <N'> generates all phrases generated by <N> except any phrases which are in said list of counter-example sentences; creating a new rule <No> such that <No> generates only phrases which are in said list of counter-example sentences and generated by <N>; and modifying a rule containing said <<START>> symbol in said parse tree such that said rule containing said <<START>> symbol ceases to generate said sentences in said list of counter-example sentences.