U.S. Philips Corporation

Adrianus C Oerlemans

Fransiscus Wilhelmus Sijstermans

A method and a device for determining the permissibility of a series of a1. . . an end symbols as being derivable by means of a set of production rules on the basis of a context-free grammar G are described. The derivation takes place by assigning dotted rules to elements Ti,j (0.ltoreq.i.ltoreq.j.ltoreq.n) (FIG. 1) of a recognition matrix by means of scan, complete and predict operations. The number of operations is of the order of (n.sup.3). In a first embodiment (n+1) processing modules (FIG. 8) are set up and the successive operations can be limited to a number of the order of (n.sup.2) . In a second embodiment 1/2(n+1)(n+2)-1 processing modules are set up and the successive operations can be limited to a number of the order of (n). The method may be applied in a translation machine.

Growing community of inventors

Eindhoven, Netherlands

Adrianus C Oerlemans