Patent ID: 8296129

Claim:
A non-transitory computer-readable non-volatile storage medium having stored thereon computer-executable instructions that, when executed by one or more processors of a computer system, cause the computer system to perform a process for inferring a grammar from a plurality of example sentences, the process including: selecting ones of said example 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 of the selected sentences, each of the rules having a left-hand side and a right-hand side; reducing the right hand side of each rule on the basis of the right hand sides of the other rules using typed leftmost reduction or typed rightmost reduction; 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; removing one or more of said one or more shortest prefix components by removing one or more of said rules; and generating a grammar on the basis of the reduced rules.