Situations where a spoken dialogue system cannot interpret a user’s utterance are a major source of frustration in humancomputer spoken dialogue. Current spoken dialogue systems generally respond with an unhelpful "I'm sorry, I didn’t understand," or something similarly uninformative. Recent work on Targeted Help has shown that giving users more appropriate feedback makes systems easier to learn and improves performance. In particular, Targeted Help can give the user an appropriate within-domain example sentence to help the user more quickly learn the system’s lexical and grammatical coverage. This paper addresses the generation problem of how to find such an example sentence. We present and evaluate four algorithms for solving this generation problem: an Iterative-Deepening (ID) algorithm, an A� algorithm, a combined A�-ID algorithm, and an anytime algorithm.