A common area of research within music technology is the automatic generation of musical accompaniment. Of particular interest is the generation of harmonic accompaniment to melody. While there are many approaches to solving this problem, the use of various types of finite state machines is popular. One such finite state machine, the finite state transducer (FST), has been used in a few accompaniment generation systems. Although the FST is widely used in speech recognition, its application in accompaniment generation systems has been relatively unsophisticated. In this paper, we introduce an improved approach to generating harmonic accompaniment to melody based on techniques used in speech recognition. In addition, we describe how we extend this method to the generation of rhythmic accompaniment. Finally, we discuss the integration of these offline accompaniment systems into a real-time system.