In this paper we propose an extension to weighted finite-state transducers in order to enable them to model context-free grammars. Classical finite-state transducers are restricted to modeling regular grammars. However, for some tasks it is necessary to use more general context-free grammars. Even some regular grammar models can be scaled down using context-free rules. The paper extents the transducers to pushdown weighted finite-state transducers and explains the decoding procedure. We apply the method to an embedded speech dialog system. Speech recognition results show that more than 80% in network size can be saved. Additionally pushdown weighted finite-state transducers clearly outperform the classic ones in terms of best recognition performance and low computation time. Altogether this extension has enabled our recognition task to be executed on a digital signal processor.

Index Terms: Weighted finite-state transducer, WFST, Language Models, Automatic speech recognition