We demonstrate the applications of Markov Chains and HMMs to modeling of the underlying structure in spontaneous spoken language. Experiments with supervised train- ing cover the detection of the current dialog state and identification of the speech act as used by the speech translation component in our JANUS Speech-to-Speech Translation System. HMM training with hidden states is used to uncover other levels of structure in the task. The possible use of the model for perplexity reduction in a continuous speech recognition system is also demonstrated. To achieve improvement over a state independent bigram language model, great care must be taken to keep the number of model parameters small in the face of limited amounts of training data from transcribed spontaneous speech.