Patent 7289950 was granted and assigned to Apple (company) on October, 2007 by the United States Patent and Trademark Office.
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.