An automated directory assistance (130) includes a training system (210) and a directory assistance system (220). The training system (210) trains and maintains the directory assistance system (220). The training system (210) includes a transcription module (310), a speech grammar estimation module (330), a listings statistics estimation module (340), and a required words determination module (350). The transcription module (310) obtains transcripts relating to directory service requests. The speech grammar estimation module (330) creates an n-gram grammar for multiple telephone numbers from the transcripts. The listings statistics estimation module (340) identifies words used to refer to each of the telephone numbers from the transcripts. The required words determination module (350) identifies at least one word that is required to request each of the telephone numbers from the transcripts. The directory assistance system (210) includes a speech recognition module (510), a listing retrieval module (520), and an accept/reject module (530). The speech recognition module (510) receives an audible request for a telephone number from a caller and generates a transcript from the audible request. The listing retrieval module (520) retrieves at least one listing corresponding to the audible request from a database using the transcript. The accept/reject module (530) determines whether to accept one or more of the listings retrieved by the listing retrieval module (520) and presents a telephone number corresponding to the accepted listing to the caller.