Extended finite state grammar for speech recognition systems

• US 7,289,950 B2
• Filed: 09/21/2004
• Issued: 10/30/2007
• Est. Priority Date: 09/29/2000
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bellegarda, Jerome R., Silverman, Kim E. A.
• Primary Examiner(s): Storm; Donald L.
• Application Number:
  US10/947,429
• Publication Number:
  US 20050038650A1
• Time in Patent Office: 1,134 Days
• Field of Search: None
• US Class Current: 704/10
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks

Abstract

An extended finite state grammar structure is generated from a finite state grammar. The extended finite state grammar structure includes word subgraphs representing a set of pre-defined word strings for words in the finite state grammar, and a set of all possible word strings for the words. The extended finite state grammar structure can be used to transform audio input into one or more of the word strings.

Claims

1. A computerized method comprising:

generating an extended finite state grammar structure comprising a first word sub-graph representing a set of pre-defined word strings for words in a finite state grammar, and a second word sub-graph representing a set of all possible word strings for the words in the finite state grammar, wherein the extended finite state grammar structure is subsequently used to transform audio input into at least one of the word strings.

2. The method of claim 1 further comprising:

assigning a probability to an arc in the second word sub-graph.

3. The method of claim 1 further comprising:

creating the set of all possible word strings.

4. The method of claim 1 further comprising:

retrieving the set of pre-defined word strings, wherein each pre-defined word string corresponds to a command in a list of recognized commands.

5. A machine-readable medium having executable instructions to cause a machine to perform a method comprising:

generating an extended finite state grammar structure comprising a first word sub-graph representing a set of pre-defined word strings for words in a finite state grammar, and a second word sub-graph representing a set of all possible word strings for the words in the finite state grammar.

6. The machine readable medium of claim 5, wherein the method further comprises:

assigning a probability to an arc in the second word sub-graph.

7. The machine readable medium of claim 5, wherein the method further comprises:

creating the set of all possible word strings.

8. The machine readable medium of claim 5, wherein the method further comprises:

retrieving the set of pre-defined word strings, wherein each pre-defined word string corresponds to a command in a list of recognized commands.

9. A computer system comprising:

a processor; and

a memory coupled to the processor through a bus, wherein the processor is configured to generate an extended finite state grammar structure, the extended finite state grammar structure comprising a first word sub-graph stored in the memory and corresponding to a set of pre-defined word strings for words in a finite state grammar, and a second word sub-graph stored in the memory and corresponding to a set of all possible word strings in the finite state grammar.

10. The system of claim 9, wherein the processor is further configured to assign a probability to an arc in the second word sub-graph.

11. The system of claim 9, wherein the processor is further configured to create the set of all possible word strings.

12. The system of claim 9, wherein the processor is further configured to retrieve the set of pre-defined word strings from the memory, wherein each pre-defined word string corresponds to a command in a list of recognized commands.

13. An apparatus comprising:

means for speech recognition;

means for semantic classification; and

an extended context-free grammar, the extended context free grammar comprising a first word sub-graph representing a set of pre-defined word strings for words in a finite state grammar, and a second word sub-graph representing a set of all possible word strings for the words in the finite state grammar, wherein the means for speech recognition outputs a word string selected from the extended context free grammar to the means for semantic classification in response to speech input into the means for speech recognition.