A System and Process For Grammatical Interference

• US 20080126078A1
• Filed: 04/29/2004
• Published: 05/29/2008
• Est. Priority Date: 04/29/2003
• Status: Active Grant

• Current Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Original Assignee: Telstra Corporation Limited (Telstra Group Ltd.)
• Inventors: Starkie, Bradford Craig
• Granted Patent: US 8,296,129 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A grammatical inference system for inferring a grammar from a plurality of example sentences. The system selects sentences having a common suffix or prefix component; identifies the other of said suffix or prefix component of each selected sentence; generating rules for generating the example sentences and the other components; reduces the right hand side of each rule on the basis of the right hand sides of the other rules; and generates a grammar on the basis of the reduced rules.

Claims

1. A process for inferring a grammar from a plurality of example sentences, including:

selecting sentences having a common suffix or prefix component;

identifying the other of said suffix or prefix component of each selected sentence;

generating rules for generating the example sentences and the other components; and

reducing the right hand side of each rule on the basis of the right hand sides of the other rules.

2. A process as claimed in claim 1, including deleting rules that violate the constraints of a target class for said grammar.

3. A process as claimed in claim 2, wherein said step of deleting includes removing one or more of left recursion, unreachable rules and badly formed signatures.

4. A process as claimed in claim 1, wherein said step of reducing includes resolving conflicts from left to right.

5. A process as claimed in claim 1, wherein said step of reducing includes resolving conflicts from right to left.

6. A process as claimed in claim 1, wherein said step of reducing is repeated until no more reductions can be made, subject to one or more constraints of the grammar.

10. A process as claimed in claim 1, including:

identifying one or more shortest prefix components common only to negative example sentences of said plurality of example sentences;

generating rules for generating said one or more shortest prefix components; and

removing one or more of said one or more shortest prefix components by removing one or more of said rules.

11. A process as claimed in claim 10, including selecting from said rules one or more rules to be unfolded on the basis of said one or more shortest prefix components;

and wherein said step of removing includes unfolding one of more of the selected rules.

12. A process as claimed in claim 1, wherein said step of reducing corresponds to one of typed leftmost reduction and typed rightmost reduction.

16. A system having components for executing the steps of any one of claims 1 to 15.

17. A computer readable storage medium having stored thereon program code for executing the steps of any one of any one of claims 1 to 15.

7. A process for inferring a grammar from a plurality of positive and negative example sentences and a starting grammar, including:

identifying one or more shortest prefix components common only to said plurality of negative example sentences;

identifying rules of the starting grammar for generating said one or more shortest prefix components; and

removing one or more of said one or more shortest prefix components by removing one or more of said rules.

8. A process as claimed in claim 7, including:

selecting from said rules one or more rules to be unfolded on the basis of said one or more shortest prefix components; and

wherein said step of removing includes unfolding one of more of the selected rules.

9. A process for inferring a grammar in the limit from a plurality of positive and negative example sentences, including:

identifying in the limit a grammar from only the positive example sentences using machine learning; and

generating, on the basis of said grammar and said plurality of positive and negative example sentences, an output grammar that can generate all of the positive example sentences but cannot generate any of the negative example sentences.

13. A process for inferring a grammar from a plurality of positive and negative example sentences, including:

generating in the limit a class of grammar from only the positive example sentences; and

removing recursion from the grammar.

14. A process as claimed in claim 13, wherein said step of removing recursion includes removing from the grammar rules that generate negative example sentences.

15. A process for inferring a grammar from a plurality of example sentences, including:

generating rules for generating said plurality of example sentences; and

reducing one or more of said rules.

18. A grammatical inference system, including a merging component for selecting sentences having a common suffix or prefix component;

identifying the other of said suffix or prefix component of each selected sentence;

generating rules for generating the example sentences and the other components;

reducing the right hand side of each rule on the basis of the right hand sides of the other rules; and

generating a grammar on the basis of the reduced rules.

19. A grammatical inference system as claimed in claim 18, including a splitting component for generating, on the basis of said grammar and said plurality of positive and negative example sentences, an output grammar that can generate all of the positive example sentences but cannot generate any of the negative example sentences.

20. A grammatical inference system as claimed in claim 18, including an unfolding component for removing recursion from said grammar.

21. A grammatical inference system as claimed in claim 18, including a conversion component for converting said grammar to a format for use in a dialog system.

22. A grammatical inference system as claimed in claim 18, wherein said format includes an SRGS grammar.

23. A grammatical inference system as claimed in claim 18, wherein said format includes program code.

24. A grammatical inference system adapted to generate rules for generating a plurality of example sentences;

and to reduce one or more of said rules.