System and Method for Converting Graphical Call Flows Into Finite State Machines

• US 20110208510A1
• Filed: 05/03/2011
• Published: 08/25/2011
• Est. Priority Date: 04/16/2004
• Status: Active Grant

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Wilson, James M., Castillo, Cecilia, Roycraft, Theodore J.
• Granted Patent: US 8,381,200 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 9/4498 Finite state machines

Abstract

A method, system and module for automatically converting a call flow into a state-based representation are disclosed. The method comprises walking a call flow and converting each page of the call flow into a rule of a higher level representation of the call flow, augmenting the higher level representation with terminal symbols representing state variable assignments and comparisons associated with decision and computation shapes in the call flow and converting the higher level representation into a state-based representation.

Claims

1. A method comprising:

receiving a call flow for a spoken dialog service;

converting, via a processor, the call flow into a higher level representation with state variable assignments and comparisons dependant on shapes in the call flow; and

converting the higher level representation into a state-based representation.

2. The method of claim 1, wherein the higher level representation is a context-free grammar representation.

3. The method of claim 1, wherein the higher level representation is a Backus-Naur Form.

4. The method of claim 1, wherein the state-based representation is a finite state machine.

5. The method of claim 3, wherein converting the call flow to the Backus-Naur Form occurs automatically via a computing device.

6. The method of claim 3, wherein converting the higher level representation into the Backus-Naur Form further comprises automatically augmenting the Backus-Naur Form with terminal symbols.

7. The method of claim 1, wherein the call flow comprises at least one page having a set of shapes having specific meanings.

8. The method of claim 7, wherein the set of shapes having special meanings comprises at least one of parallelograms representing rules, lines representing dialog inputs, rectangular boxes representing dialog outputs or actions, diamonds representing Boolean decision functions, hexagrams representing calculation and assignment functions and annotation shapes representation comments.

9. The method of claim 3, wherein the state-based representation is a finite state machine, and wherein a grammar compiler is used to convert the Backus-Naur Form into the finite state machine.

10. The method of claim 9, wherein the finite state machine may be used by at least one spoken dialog tool to perform generation and testing functions associated with a spoken dialog service.

11. The method of claim 1, wherein converting the call flow into the higher level representation uses rules which provides labels to shapes and transitions of the call flow.

12. The method of claim 1, further comprising generating a unique terminal symbol in the higher level representation that shadows each rule, input, output, decision and calculation within the call flow.

13. A system for converting a call flow for a spoken dialog service into a state-based representation, the system comprising:

a processor;

a first module configured for controlling the processor to convert the call flow into a higher level representation with state variable assignments and comparisons dependant on shapes in the call flow; and

a second module configured for controlling the processor to convert the higher level representation into a state-based representation.

14. The system of claim 13, wherein the higher level representation is a context-free grammar representation.

15. The system of claim 13, wherein the higher level representation is a Backus-Naur Form.

16. The system of claim 13, wherein the state-based representation is a finite state machine.

17. A non-transitory computer-readable storage medium storing instructions which, when executed by a computing device, cause the computing device to convert a call flow for a spoken dialog service into a state-based representation, the instructions comprising:

receiving the call flow for the spoken dialog service;

converting the call flow into a higher level representation, having state variable assignments and comparisons dependant on shapes in the call flow; and

converting the higher level representation into the state-based representation.

18. The non-transitory computer-readable medium of claim 17, wherein a grammar compiler is used to convert the higher level representation into the state-based representation.

19. The non-transitory computer-readable medium of claim 18, wherein the grammar compiler augments converting the higher level representation into the state-based representation with suffixes associated with a special meaning.

20. The non-transitory computer-readable medium of claim 17, further comprising instructions to:

create a unique terminal symbol in the higher level representation that shadows each rule, input, output, decision, and calculation within the call flow.