Dynamic programming parsing for context-free grammars in continuous speech recognition

The use of context-free grammars in automatic speech recognition is discussed. A dynamic programming algorithm for recognizing and parsing spoken word strings of a context-free grammar is presented. The time alignment is incorporated in to the parsing algorithm. The algorithm performs all functions simultaneously, namely, time alignment, work boundary detection, recognition, and parsing. As a result, no postprocessing is required. From the probabilistic point of view, the algorithm finds the most likely explanation or derivation for the observed input string, which amounts to Viterbi scoring rather than Baum-Welch scoring in the case of regular or finite-state languages. The algorithm provides a closed-form solution. The computational complexity of the algorithm is studied. Details of the implementation and experimental tests are described