15. A computer-readable storage device having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising: receiving, during a natural language dialog between a user and the computing device, an utterance; generating a semantic and syntactic graph using the utterance, the semantic and syntactic graph comprising an initial state and a final state associated with the utterance and being generated by adding transitions that encode semantic and syntactic categories of words or word sequences within the utterance; extracting possible combinations of features from the semantic and syntactic graph, to yield extracted n-grams; comparing the extracted n-grams to previously classified n-grams, to yield a comparison; classifying the utterance as being associated with a call type based on the extracted n-grams and the comparison, wherein the call type is chosen from a predefined set of call types and wherein the call type characterizes a communication, to yield a classified utterance; and responding, with a computer-generated response, to the user in the natural language dialog based on the classified utterance.
15. A computer-readable storage device having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising: receiving, during a natural language dialog between a user and the computing device, an utterance; generating a semantic and syntactic graph using the utterance, the semantic and syntactic graph comprising an initial state and a final state associated with the utterance and being generated by adding transitions that encode semantic and syntactic categories of words or word sequences within the utterance; extracting possible combinations of features from the semantic and syntactic graph, to yield extracted n-grams; comparing the extracted n-grams to previously classified n-grams, to yield a comparison; classifying the utterance as being associated with a call type based on the extracted n-grams and the comparison, wherein the call type is chosen from a predefined set of call types and wherein the call type characterizes a communication, to yield a classified utterance; and responding, with a computer-generated response, to the user in the natural language dialog based on the classified utterance. 20. The computer-readable storage device of claim 15 , wherein generating the semantic and syntactic graph associated with the utterance further comprises adding transitions encoding semantic and syntactic categories of words to a word graph.