Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
4599691
Sakaki , ; et al.
July 8, 1986
Title
Tree transformation system in machine translation system
Abstract
A mechanical translation system is provided to obtain a sentence of target language from the tree expression of source language. The processing progresses as follows: First, a pattern which coincides with partial structure, including the highest node, of the tree fragment chosen, is selected among patterns previously contained in the pattern dictionary. The pattern has a production rule attached to the pattern. The production rule takes "extraction information" which is composed of information in the source language tree fragment concerning the part outside of and under the above mentioned partial structure and "instruction information" which is attached to the highest node of the tree fragment, as input information and generates a tree fragment in target language corresponding to the source language tree fragment and also "instruction information" to be attached to the border nodes of the partial structure and other parts in the source language tree fragment which consists of memorizing the target language tree fragment and erasing the partial structure from the source language tree fragment and bringing back to the memory to contain target language tree fragments, thus produced normally plural "child" tree fragments. After processing a plurality of target language tree fragments contained in the corresponding memory and uniting them into a single tree producing the tree of target language tree, from which the sentence in target language is obtained immediately.
Inventors:
Sakaki; Hiroshi
(Tokyo,
JP
)
, Hashimoto; Kazuo
(Tokyo,
JP
)
Assignee:
Kokusai Denshin Denwa Co., Ltd.
(Tokyo,
JP
)
Appl. No.:
494361
Filed:
May 13, 1983
Foreign Application Priority Data
May 20, 1982 [JP] 57-83961
Current U.S. Class:
704/2
Current International Class:
G06F 17/28 (20060101)
Field of Search:
434/157 364/419,9MSFile
U.S. Patent Documents
4502128
February 1985
Okajima et al.
Foreign Patent Documents
102071
Aug., 1980
JP
Other References
Amamiya, M. et al., "Japanese Question-Answering System on the Topic of Figure Manipulations", Review of the Electrical Communications Labs, vol. 26, Nos. 7-8, Jul.-Aug. 1978, 1045-54. .
Tsujii, Jun-ichi, "The Transfer Phase in an English-Japanese Translation System", Coling 82, J. Horecky, North-Holland Publishing Company, 1982..~
Primary Examiner:
Smith; Jerry
Assistant Examiner:
Jablon; Clark A.
Attorney, Agent or Firm:
Collard, Roe & Galgano
Claims
What is claimed is:
1. A machine translation system (FIG. 7) which generates sentences in target language using tree structure expression in source language comprising;
a pattern dictionary (PTD, FIG. 7) for storing a table of target language and source language,
means (PPD, FIG. 7) having at least a first shift register (PPA) having source tree patterns from said pattern dictionary, a second shift register (PPB) having source tree which is to be translated, a coincidence detector (CSD) for comparing outputs of said first (PPA) and second (PPB) shift registers; for providing coincident pattern of patterns contained in the pattern dictionary and partial pattern of tree structure in source language including the topmost mode of said tree structure;
means (SDS, FIG. 7) for producing a pattern in said target language and an instruction to lower layer utilizing the information of information from instruction from upper layer, extraction information (EXG, FIG. 7), and production rule (stored in PRT, FIG. 7) peculiar to said coincident pattern;
means (INA, MPE, FIG. 7) having a first shift register (AAA) storing said instruction to lower layer, a second shift register (AAB) storing said tree structure, AND-OR logic means for coupling the output of said first shift register (AAA) to the output of said second shift register (AAB) to eliminate said coincident pattern;
means (SPC, FIG. 7) having a first shift register (UAA) storing separated partial target trees, a second arithmetic register (UAB) for performing operation to signal in said first shift register (UAA), and a third shift register (UAC) for storing the output of said second register (UAB), so as to produce a final target language tree which is connected to the result of said partial target tree through repeating said means (SPC) until the whole of said tree structure is eliminated; and
means (SPL, FIG. 7) for receiving the output of said SPC means and generating final sentence in target language.
Description
BACKGROUND OF THE INVENTION
As for machine translation system, many systems have been proposed so far. The most popular ones have a feature that they generate target language or language to be translated into, after introducing sentence in source language or language to be translated from, and applying the process consisting of extracting the meaning of the introduced sentence in source language, which process should be called processing into deep structure. Though these types of methods conform with theories in linguistics, they are not well suited to accept special expressions a little out of general rules of language in spite of the fact that these expressions inevitably occur in natural language such as Japanese, and to reflect these expressions to translation.
SUMMARY OF THE INVENTION
It is an object, therefore, of the present invention to overcome the disadvantages of a prior art by providing a new and improved machine translation system.
It is also an object of the present invention to provide a machine translation system which can translate sophisticated language like Japanese.
This invention treats language as a set of specific patterns and conducts translation by alloting corresponding patterns in target language for each pattern in source language, and as a result, can conduct sophisticated translation by including patterns corresponding to these specific expressions. Following is the detailed explanation of the invention.
BRIEF DESCRIPTION OF THE DRAWING
The foregoing and other objects, features, and attendant advantages of the present invention will be appreciated as the same become better understood by means of the following description and accompanying drawings wherein;
FIG. 1 shows application result of pre-processing (ii) to the input sentence.
FIG. 2 shows application result of pre-processing (iii).
FIG. 3 shows application result of pre-processing (iv).
FIG. 4 shows the figure of input tree structure.
FIG. 5 shows the tree structure of FIG. 4 totally covered with transformation patterns.
FIG. 6 consists of figures for transformation patterns amoung among which FIG. 6(a) shows transformation pattern P-1, FIG. 6(b) shows transformation pattern P-2, FIG. 6(c) shows transformation pattern P-3, FIG. 6(d) shows transformation pattern P-4, FIG. 6(e) is for transformation pattern P-I, FIG. 6(f) is for transformation pattern P-play, FIG. 6(g) is for transformation pattern P-the, FIG. 6(h) is for transformation pattern P-piano and FIG. 6(i) is for transformation pattern P-period.
FIGS. 7, 7(a), 7(b) and 7(c) are figures of composition of machine translation system of this invention.
FIG. 8 is figures concerning target language pattern for the transformation pattern P-1. FIG. 8(a) is the figure for body of target language pattern and FIG. 8(b) is the figure for structure order correspondence table.
FIG. 9 is figure for partial pattern P-1 with attachment of node number.
FIG. 10 is arrangement, concerning partial pattern P-1, of node numbers in source language in accordance with structure order in source language pattern.
FIG. 11 is arrangement, concerning partial pattern P-1, of node numbers in accordance with structure order in target language.
FIG. 12 is figure of target language tree structure for the partial pattern P-1.
FIG. 13 shows the instruction to lower layer concerning partial pattern P-1.
FIG. 14 is the figure of input tree structure with instruction for partial pattern P-1.
FIG. 15 shows rest tree structure after the elimination of trees concerning partial pattern P-1.
FIG. 16 is the figure of handled tree structure at the beginning of second round of operation.
FIG. 17 is the figure of not handled tree structure at the beginning of second round of operation.
FIG. 18 shows the figure of handled tree structure affected by separation of instruction.
FIGS. 19(a), 19b), 19(c) and 19(d) show the extraction indication for partial pattern P-2. It consists of four kinds of extraction indications.
FIG. 20 is the figures for target language pattern P'-2-1. FIG. 20(a) is the figure for body of target language pattern and FIG. 20(b) is the figure for structure order correspondence table.
FIG. 21 is the figures for target language pattern P'-2-2. FIG. 21(a) is the figure for body of target language pattern and FIG. 21(b) is the figure for structure order correspondence table.
FIG. 22 shows a utilization method of "A".
FIG. 23 is the figure of tree structure with node number attached for the partial pattern P-2.
FIG. 24 is structure for pattern P-2 where node number of source language is arranged according to the structure order in source language pattern.
FIG. 25 is structure for the pattern P-2 where node number is arranged in the structure order of target language structure.
FIG. 26 is the figure of target language tree structure for partial pattern P-2.
FIG. 27 shows the instruction to lower layer concerning partial pattern P-2.
FIG. 28 is the figure of handled tree structure at the second round of operation with attached instruction for the partial pattern P-2.
FIG. 29 is the figure for rest tree structure after the erasing of partial pattern P-2.
FIG. 30 is the figure of handled tree structure for the third round of operation.
FIG. 31 is the figure of not handled tree structure for the third round of operation.
FIG. 32 is the figure for handled tree structure for the third round of operation after the separation of instruction.
FIG. 33 is the figure of target language pattern P'-4-1.
FIG. 34 shows instruction to lower layer concerning partial pattern P-4.
FIG. 35 is the figure for tree structure with node number for partial pattern P-4.
FIG. 36 is arrangement, concerning partial pattern P-4, of node numbers in accordance with structure order in source language.
FIG. 37 is arrangement, concerning partial pattern P-4, of node numbers in accordance with structure order in target language.
FIG. 38 is figure of target language tree structure concerning partial pattern P-4.
FIG. 39 shows memory contents of output tree structure memorizing part SPM after the third round of operation.
FIG. 40 is the figure of handled tree structure for third round of operation with attached instruction for partial pattern P-4.
FIG. 41 is the figure of handled tree structure at the fourth round of operation.
FIG. 42 is the figure of handled tree structure at the fourth round of operation after the separation of instruction.
FIG. 43 is the figure of target language pattern P'-1-1.
FIG. 44 is the figure of instruction to lower layer concerning partial pattern P-I.
FIG. 45 is tree structure with attachment of node number concerning partial pattern P-I.
FIG. 46 is arrangement, concerning partial pattern P-I, of node numbers in accordance with structure order in source language pattern.
FIG. 47 is arrangement, concerning partial pattern P-I of node numbers in accordance with structure order in target language structure.
FIG. 48 is the figure of target language tree structure for partial pattern P-I.
FIG. 49 is the figure for partial pattern P-I as handled tree structure with attachment of instruction at the fourth round of operation.
FIG. 50 is the figure of handled tree structure at the fifth round of operation.
FIG. 51 is the figure of not handled tree structure at the fifth round of operation.
FIG. 52 is the figure of handled tree structure after the separation of instruction.
FIG. 53 is the figures of target language patterns for the partial pattern P-play. FIG. 53(a) shows that of P'-play-1, FIG. 53(b) shows that of P'-play-2 and FIG. 53(c) shows that of P'-play-3.
FIG. 54 is figures concerning the pattern P-kiss. FIG. 54(a) shows the figure of source language pattern P-kiss. FIG. 54(b) shows the figure of target language pattern P'-kiss-1.
FIG. 55 is arrangement, concerning partial pattern P-play, of node numbers in source language in accordance with structure order in source language pattern.
FIG. 56 is figure of target language tree structure for partial pattern P-play.
FIG. 57 shows the memory content of output tree structure memorizing part SPM at the end of fifth round of operation.
FIG. 58 shows instruction to lower layer concerning partial pattern P-play.
FIG. 59 is the figure of handled tree structure for partial pattern P-play with attachment of instruction.
FIG. 60 is the figure of handled tree structure at the sixth round of operation.
FIG. 61 is the figure of not handled tree at the sixth round of operation.
FIG. 62 shows the memory contents of output tree structure memorizing part SPG after the completion of operation of circulation.
FIG. 63 is the figure of target language pattern P'-3-1.
FIG. 64 is the figure of target language pattern P'-the-1.
FIG. 65 is the figure of target language pattern P'-piano-1.
FIG. 66 is the figure of target language pattern P'-period-1.
FIG. 67 shows the result of first connecting operation at output tree structure connecting part SPC.
FIG. 68 shows the remaining part after the first connecting operation at output tree structure connecting part SPC.
FIG. 69 shows result of merge at output tree structure connecting part SPC.
FIG. 70 shows the output of target language pattern linearizing part SPL.
FIGs. 71, 71(a) and 71(b) are the figures of tree structure deciding part HTD realized by electronic circuit.
FIG. 72 is state diagram of tree structure deciding part HTD.
FIGS. 73, 73(a) and 73(b) are the figures of partial pattern finding part PPD realized by electronic circuit.
FIG. 74 is state diagram of partial pattern finding part PPD.
FIG. 75 is the figure of an example of contents in pattern dictionary PTD.
FIG. 76 if figure of a portion of extraction generating part EXG realized by electronic circuit.
FIGS. 77, 77(a) and 77(b) are figures of another portion of extraction generating part EXG realized by electronic circuit.
FIG. 78 is state diagram of extraction generating part EXG.
FIGS. 79, 79(a) and 79(b) are figures of node number dealing part NMH realized by electronic circuit.
FIG. 80 is state diagram of node number dealing part NMH.
FIGS. 81, 81(a) and 81(b) are the figures of instruction dealing part INH realized by electronic circuit.
FIG. 82 is the state diagram of instruction dealing part INH.
FIGS. 83, 83(a) and 83(b) are the figures of first number arranging part NNA1 realized by electronic circuit.
FIG. 84 is state diagram of first number arranging part NNA1.
FIGS. 85, 85(a) and 85(b) are the figures of second node number arranging part NNA2 realized by electronic circuit.
FIG. 86 is state diagram of second number arranging part NNA2.
FIGS. 87, 87(a) and 87(b) are the figures of output tree structure generating part SPG realized by electronic circuit.
FIG. 88 is state diagram of output tree structure generating part SPG.
FIGS. 89, 89(a) and 89(b) are the figure of output tree structure connecting part SPC realized by electronic circuit.
FIG. 90 is the figure of limited coincidence detector CSG.
FIG. 91 is state diagram of output tree structure connecting part SPC.
FIGS. 92, 92(a) and 92(b) are the figures of target language pattern linearizing part SPL realized by electronic circuit.
FIG. 93 is state diagram of target language pattern linearizing part SPL.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
The processing concerning the invention can be divided into two phases, one of which is pre-processing needed to extract information to be introduced to the system of this invention, from sentence in source language, another of which is proper processing of this invention. The pre-processing is explained first. The pre-processing consists of the following steps.
(i) Putting in a sentence in source language which must be translated.
(ii) Introducing nodes which have names of respective word names contained in aforementioned sentence and composing a set of nodes by arranging them in a row at the order of the position in the sentence. These nodes will constitute nodes of lowest layer in tree structure and called terminal nodes.
(iii) Deciding category names of whole words in the sentence by the use of a dictionary. Putting, after above processing, a node of category name on each corresponding node of word name and connecting each pair of nodes by a line. Lines connecting nodes are called arcs. The processing here is called "non terminalization", as the processing is constituted of putting non terminal nodes on the terminal nodes corresponding to word names. The category classification here is much detailed one compared with usual "part of speech" classification.
Following is the processing proper to this invention.
(iv) Composing a non separate tree structure by using a set of rules called parsing grammer the composing element of which unites several nodes adjoined to each other into one node higher by one layer, and by connecting by arcs between the higher node and every united node in lower layer and by repeating above processing. The tree structure is called tree structure of input sentence. A tree is a configuration which has no path obtained by tracing different arcs and nodes alternatively and returning to the starting node.
(v) Affixing a number to every node in tree structure. The way of numbering can be arbitrary, nevertheless the numbering method in which the highest node is affixed by 1 and a node other than the highest node is affixed by number of the node higher by one layer and directly connected to the former one, but supplemented by the number corresponding to the number of the order of the former node counted from the left, at the lowest place, is used here.
Above is the explanation of processing including pre-processing and proper processing. Though the "non terminalization" grammar shown in (iii) is a kind of parsing grammar, it is treated as different from parsing grammar because it has peculiar character in that it is applied prior to parsing grammar and it depends on word names. Many kinds of elements in parsing grammar are used in the processing concerning the invention. Hereafter an element of parsing grammar is also called parsing grammar where confusion is not expected.
Now pre-processing and processing proper to this invention are explained successively using an example. A block diagram is used at the explanation of the treatment on the example. The English sentence used in the example is:
As a result of pre-processing (iii) the configuration in FIG. 1 is obtained. Every square represents a node which has name written in it. After the pre-processing (iii), the configuration in FIG. 2 is obtained. N which is not expressed in the figure represents noun in general. VT, DET, and END represent transitive verb, determinative and end mark respectively. As for noun N, more detailed category classification in which NPO and NMI correspond pronoun and musical instrument respectively, is adopted. End mark denoted by END includes .(period), ?(question mark) and -(exclamation mark). After the processing of (iv), tree structure of input sentence shown in FIG. 3 is obtained. S, T and NP which are newly introduced, denote sentence, text and noun phrase respectively. Region of L-I, L-play, L-the, L-piano and L-period in the FIG. 3 denote application region for non terminalization grammars of I, play, the, piano and period respectively and K-1, K-2, K-3 and K-4 denote application region of four kinds of parsing grammars. These grammars expressed in the shape of equation for representation of parsing grammar are shown below. As for non terminalization grammar, L-I is expressed as:
L-play is expressed as:
L-the is expressed as:
L-piano is expressed as:
and finally L-period is expressed as:
Concerning parsing grammar, K-1 is expressed as:
K-2 is expressed as:
K-3 is expressed as:
and finally K-4 is expressed as:
Non terminalization grammars among these grammars are used to express catagory names of words and parsing grammars, which are deduced from theories of natural language paying attention to the convenience in translation are used to unite more than one node into upper concept. These amount to several hundred in usual translation systems. In the equations as shown in FIGS. (2)-(10), one or more nodes which must be united and which are situated in lower layer are written in right hand and one node obtained by the unification is written in left hand. Among parsing grammars, K-1 denoted in Eq. (7) shows that text is composed of sentence and end mark. K-2 expressed in Eq. (8) corresponds to sentence pattern of transitive verb with one object. K-3 expresses that determinative and musical instrument name makes noun phrase and K-4 shows that pronoun alone will make noun phrase. After the processing of (iv), configuration in FIG. 4 is obtained. Number for each node is shown in the lower part of each node. Numbers are used to construct sentence tree structure of target language after the time when the input sentence tree structure have been split into several patterns and each so generated pattern is transformed into tree structure of target language. Configuration shown in FIG. 4 is input information for machine translation system of this invention. This is the tree structure of source language which is English. The explanation for the invention is done using this example and following the method of this invention until the generation of Japanese sentence.
For convenience of explanation, the situation where tree structure of input sentence which is shown in FIG. 4 is totally covered by transformation patterns is shown in FIG. 5. Though the patterns are obtained by the from top to bottom order successively, whole patterns are shown for the sake of explanation. These transformation patterns respectively correspond to minimum meaning units for translation. As easily understood by comparison of FIG. 5 and FIG. 3, transformation patterns and parsing grammars are all the same, but generally speaking transformation patterns and parsing grammars are chosen from a different standard and are apt to be different. A transformation pattern connecting a terminal node and a non-terminal node directly on the terminal node, and, as a result, having strong relation with word constituting specific terminal node, is given a name, such as P-I or P-play, which name is composed by connecting the name of the terminal node after the letter P which means transformation pattern. For the other types of transformation patterns, the names, such as P-1 or P-2, composed by connecting numbers after P is given. Transformation patterns are chosen following the standards that they, as a whole, can cover tree structure of input sentence totally, and that they each have unique highest nodes and the nodes common to the node contained in patterns of higher layer. The transformation patterns P-1, P-2, P-3, P-4, P-I, P-play, P-the, P-piano and P-period are again shown in FIG. 6(a) through FIG. 6(h).
Following is the description of machine translation of the type of the invention accommodating tree structure of the input sentence shown in FIG. 4. The composition is shown in FIG. 7. First the names of composing parts are given. PTD, ITM, CTM, HTD, HTM, NHM, HTA, PPD and MPM are pattern dictionary, input tree structure memorizing part, present tree structure memorizing part, handled tree structure deciding part, handled tree structure memorizing part, not handled tree structure memorizing part, tree structure affixing part, partial pattern finding part and pattern memorizing part respectively. MPR, MER and PRT are pattern memorizing region, extraction indication memorizing region and production rule memorizing region respectively and these three as a whole constitute memorizing region of MPM, the pattern memorizing part. SDS, IHP, IET, NMP, NNH, EXG, INM, INA, MPE, RTM, SPM, NNA, SPG, SPA, PGM, SPC, SPL and STM are output deciding part, separating part, tree structure memorizing part, node number affixing part, node number processing part, extraction generating part, instruction memorizing part, instruction affixing part, erasing part, rest tree structure memorizing part, output tree structure memorizing part, node number arranging part, output tree structure generating part, output tree structure affixing part, output tree structure group memorizing part, output tree structure connecting part, target language pattern linearizing part and output sentence memorizing part respectively.
Following is the operation of the configuration of FIG. 7 for the input shown in FIG. 4. The input shown in FIG. 4 is first memorized in input tree structure memorizing part ITM and, because no output from tree structure affixing part HTA is present through the fact that operation is at an early stage, output from ITM is sent to present tree structure memorizing part CTM unaltered. This output is sent to handled tree structure deciding part HTD and then immediately sent to handled tree structure memorizing part HTM as there is only one tree structure. Nothing is sent to not handled tree structure memorizing part NHM. Output of the HTM is sent to separating part IHP. IHP is the part where the separation of instruction and body of the tree structure is done. The system is at most early phase of operation and there is no instruction, consequently the output to the output deciding part is information of no instruction. Ultimately the input tree structure shown in FIG. 4 is introduced to tree structure memorizing part IET unaltered. The output which is tree structure deprived of instruction, is introduced into partial pattern finding part PPD.
The examination of coincidence by piling up the tree structure of the type of FIG. 4 and many tree structure terms in pattern dictionary PTD is conducted and, as a result, the tree structure which is the partial tree structure of the input tree structure and has the same highest node as the one in the tree structure of FIG. 4 is found. In the pattern dictionary, many tree structure patterns are registered in the shape shown in FIG. 6. The present output of the partial pattern finding part PPD is the pattern P-1 shown in FIG. 6(a) and the information telling the pattern is selected, which is brought to pattern memorizing part MPM. The part among the parentheses will be explained later. MPM obtains the information concerning P-1 through the information and pattern dictionary PTD. These consist of, structure of the pattern itself, namely the information shown in FIG. 6(a), extraction indicating information, namely the extraction indicating information concerning the part outside of present pattern in the tree structure, memorized in the tree structure memorizing part IET and also production rule information, namely indication of operation after the extraction indication is obtained, and are memorized in pattern memorizing region MPR, extraction indication memorizing region MER and production rule memorizing region PRT respectively. Concretely speaking, the contents of the MPR is the structure in FIG. 6(a) and contents of MER is the information of no instruction and contents of PRT is a table shown in Table 1.
TABLE 1 ______________________________________ input output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ -- -- P'-1-1 ______________________________________
The table indicates the treatment of the pattern P-1 and shows that the treatment is done irrespective of the instruction from upper layer and that the extraction operation which is extraction of structure outside and lower than the pattern, is not done and, as a consequence, treatment is done without using information concerning extraction operation and that the target language pattern of P'-1-1 is used and that no instruction is sent to lower layer. The detailed operation according to the table is explained later. Structure extraction indicating information from extraction indication memorizing region MER and information concerning handled tree are sent to extraction generating part EXG, nevertheless, the output of EXG which is extraction information is the information of no instruction and introduced to the output deciding part SDS. Further instruction from upper layer comes from separating part IHP to SDS but this is also information of no information. To SDS comes also a rule called production rule shown in Table 1 and depicting the method for processing the pattern P-1. Here it shows that there is only one candidate for output which tells that target language pattern P'-1-1 should be sent to output tree structure memorizing part SPM and that instruction information of no information should be sent to instruction memorizing part INM. Target language pattern consists of target language pattern itself shown in FIG. 8(a) and FIG. 8(b) which is structure order correspondence table showing the correspondence of specific node in source language pattern and specific node in target language pattern. The nodes in target language pattern itself have an empty column in which the node number is accommodated at a later stage. Presently, for the sake of explanation, there are numbers in parentheses which have no relation with the operation of the system of this invention. The symbol with prime shows that the symbol is in the target language tree structure. T', S', and END' denote text in target language, sentence in target language and end mark in target language.
Following is the explanation for structure order correspondence table as is shown in FIG. 8(b). The structure in FIG. 6(a) is source language pattern and the structure in FIG. 8(a) is target language pattern. When numbering method used in FIG.
4 is applied to the three nodes in FIG. 6(a), the numbers in the parentheses in FIG. 6(a) are obtained. Here the dictionary order where a number is thought to be a word and the word with less number at the same position from the left has the priority at the dictionary. When nodes in source language pattern which is FIG. 6(a) are arranged according to above-mentioned dictionary order, the row is obtained to be T(1), S(11), END(12). This type of arrangement of node is said to be arrangement of node in structure order. Similarly this kind of operation can be done for target language pattern shown in FIG. 8(a) and the result, when numbering in the parentheses in the figure is done and the node is arranged at the above-mentioned dictionary order or structure order, is obtained to be, T'(1), S'(11) and END'(12). As the designation is done in which the correspondence of T-T', S-S', END-END' is established between nodes of source language and these of target language, the node of the order number 1
in target language tree structure correspond also to the node of the order number 1 at the target language tree structure. As this situation is true also for the nodes of the order 2 and 3, the structure order correspondence table in FIG. 8(b) which contains the order of 1, 2, 3 is obtained. The structure order correspondence table will contain the order of 2, 3, 1, where the structure order of the node in the target language tree structure, which corresponds to the node of structure order number 1
in source language, is 2 and where second ordered node correponds to the third ordered one and also third ordered one corresponds to first ordered one. It must be noted that numbers in parentheses affixed in nodes in FIG. 6(a) and FIG. 8(a) are, as explained partially earlier, only for explanation of structure order and have nothing to do with the operation concerning this invention. The node number affixing part NMP receives tree structure shown in FIG. 4 from tree structure memorizing part IET and tree structure input shown in FIG. 6(a) from pattern memorizing region MPR and generates partial pattern with node number shown in FIG. 9.
Node number processing part NNH produces the structure in FIG. 10 using the structure of FIG. 9. This is arrangement of node number of source language in present pattern, according to the structure order. Node number arranging part NNA arranges node number according to the structure order in target language structure shown in FIG. 11 using the output of output tree structure memorizing part SPM shown in FIG. 8(b). In this case the order in FIG. 10 appears in FIG. 11 unaltered according to the structure order correspondence table. On the basis of output of NNA shown in FIG. 11 and the output of output tree structure memorizing part SPM which is structure order correspondence table shown in FIG. 8(b), the processing in which empty columns in every node number shown in FIG. 8(b) filled presently with numbers in parentheses is filled up according to structure order, is conducted at the output tree structure generating part SPG, producing tree structure of target language. This signal is introduced to output tree structure memorizing part SPA and memorized at output tree structure group memorizing part PGM coexisting with former memory contents of the part. Nevertheless memory contents of PGM become tree structure of FIG. 12, because there are no other tree structures in PGM except above tree structure, as the system is on early stage of operation.
Output deciding part SDS sends target language patterns shown in FIGS. 8(a), (b) and sends, as the other output, instruction to lower layer shown in Table 1 as the other output. It is composed of instruction to nodes on the border to the lower pattern and expressed as pair of node name and instruction. Present case is of no instruction as shown in Table 1. Instruction to lower layer in Table 1 is actually written as shown in FIG. 13. Namely, no instruction which means there is no instruction to the node is written in the instruction columns attached at the left of border nodes S and END. SDS output shown in FIG. 13, via instruction memorizing part INM, arrives at the input of instruction affixing part INA together with tree structure shown in FIG. 4 which is output of tree structure memorizing part IET, producing tree structure shown in FIG. 14. The output is introduced to erasing part MPE, where present pattern of FIG. 6(a) is erased excluding border nodes. The standard of processing here is that node higher than ones having instruction including no instruction information should be eliminated. As a result of the operation, rest tree structure information shown in FIG. 15 is introduced to rest tree structure memorizing part RTM. The present contents consist of 2 tree structures arranged in the order shown in FIG. 15. This makes the input to tree structure affixing part HTA. As the system is at early stage of operation, there is no information from not handled tree finding part NHM and consequently tree structure of FIG. 15 is memorized at present tree structure memorizing part CTM. This makes the end of processing for pattern P-1 shown in the FIG. 6(a) resulting in the situation where tree structure shown in FIG.
12 is memorized in output tree structure group memorizing part PGM and 2 tree structures shown in FIG. 15 are memorized in present tree structure memorized part CTM at the order of the figure.
Following is the operation of the system at the second round. At the beginning of the first round, the tree structure in FIG. 4 was memorized at the present tree structure memorizing part CTM whereas now, at the beginning of second round, group of 2 trees shown in FIG. 15 is memorized. This is introduced to the handled tree structure deciding part HTD where one of the trees at the present tree structure memorizing part CTM is decided to be handled tree structure and is sent to handled tree structure memorizing part HTM whereas the other part is sent to not handled tree structure memorizing part NHM as tree not to be handled at present. As the choice of tree structure does not affect the operation, as a whole, the leftest tree structure is always chosen to be handled. Consequently handled tree structure deciding part HTD sends tree structure of FIG. 16 to handled tree structure memorizing part HTM and also sends tree structure shown in FIG. 17 to not handled tree structure memorizing part NHM. The tree structure in FIG. 16 is sent to separating part IHP where instruction and body of tree structure are separated. As there is also no instruction, instruction information to output deciding part SDS is information of no information. The tree structure of FIG. 18 which is made from tree structure of FIG. 16 through elimination of instruction information is sent to tree structure memorizing part IET and memorized there. Tree structure in FIG. 18 is sent to various parts but at first it is introduced to partial pattern finding part PPD, where the test for coincidence of tree structure in FIG. 18 and various tree structures in pattern dictionary PTD is done selecting a tree which is partial tree of tree structure in FIG. 18 and has the same highest node. The output of partial pattern finding part PPD is the partern P-2 which is shown in FIG. 6(a) and the information that this pattern was selected comes to pattern memorizing part MPM. MPM obtains information concerning pattern P-2
from the information and pattern dictionary PTD and memorizes three kinds of information thus obtained in three memorizing regions in the MPM. Tree structure of FIG. 6(b) is memorized at pattern memorizing part MPR in unaltered shape and extraction indication shown in FIGS. 19(a), (b), (c) and (d) respectively is memorized in extraction indication memorizing region MER and table of production rule shown in Table 2 is memorized at production rule memorizing region PRT.
TABLE 2 __________________________________________________________________________ Input Output Instruction First Second Third Fourth Target Instruction from upper extraction extraction extraction extraction language to lower layer information information information information pattern layer __________________________________________________________________________ -- * play.hoarfrost.NMI * * P'-2-1 hiki (VT) -- * play.hoarfrost.NSP * * P'-2-1 si (VT) -- * play.hoarfrost.NRO * * P'-2-1 enji (VT) -- * kiss.hoarfrost.-- * * P'-2-2 -- __________________________________________________________________________
Tree structure shown in FIGS. 19(a), (b), (c) and (d) comes to extraction generating part EXG as extraction information. The node name ADJ newly introduced in FIG. 19 corresponds to adjective. On the other hand, the output of tree structure memorizing part IET shown in FIG. 18 comes in to the part. Extraction indication information indicates that information concerning lower layer downward of pattern P-2 shown in FIG. 6(b) must be obtained from tree structure in FIG. 18. Extraction indication, as a consequence, has the shape of pattern P-2 attached with affixed part for acquisition of information from lower layer. Acquisition of instruction information is conducted by piling up each figure in FIG. 19 with FIG. 18. At the piling up various arbitrarization measures and inspection measures are taken. The mark for these measures are A.sub.o, A.sup.o, E.sub.o and E.sup.o in the FIG. 19. A.sub.o denotes that the part corresponding to A.sub.o is arbitrary including structure of tree structure with node contained in the tree, at the decision of success or fail in piling up. A.sup.o denotes, together with the measures shown above, the part corresponding to A.sup.o must be obtained. E.sub.o denotes that one node at the part is arbitrary at the piling up. E.sup.o denotes that, together with the measures taken for E.sub.o, the name of the node must be obtained as extraction information. Extraction indication information and extraction information are named by number for each tree structure at piling up. For example FIG. 19(a) is first extraction indication information and thus obtained extraction information is called first extraction information and so on. Where piling up is not established including arbitrarization, the no piling up information is sent and when piling up is established, the output requested by A.sup.o and E.sup.o are generated keeping the order of left to right excluding the case of no request where a blank is generated. According to request, number of extraction indication information can be increased accompanying minute classification and making complex of tree structure constituting extraction indication information and, as a consequence, processing for the pattern presently dealt with can be optimized. When number of extraction indication information is increased, necessary information can be obtained using only A.sub.o and E.sub.o namely information obtained solely by piling up. Thoroughly pursuing these measures, information can be obtained without using even A.sub.o and E.sub.o through the measure in which every possibility is coded for extraction information. From above, the fact that extraction indication information can be obtained without introducing arbitrarizing and inspection measures at piling up is understood, nevertheless, these measures concerning A.sub.o, A.sup.o, E.sub.o and E.sup.o makes number of extraction indication information smaller and labour of decision less. Convenient arbitrarizing and inspection measures, for example the measure to obtain terminal node under node with specific name, can be conceived but, nevertheless, only A.sub.o, A.sup.o, E.sub.o and E.sup.o are used here for extraction indication information from the reason that necessary information with optimum labor can be obtained. The extraction information mentioned above is for acquisition of node names in tree structure. On the other hand it is also possible for a node, which is one corresponding to category name and directly on the terminal node, that subsidiary information, for example sort of conjunction for verb etc., can be affixed to the node as comments and that the comment is inspected together with the name of category node giving rise to a part of extraction information. Table 2 is similar to Table 1 and the contents of the table are rules called production rule which describe the method of processing the pattern P-2 using extraction information obtained through extraction indication information and which are affixed to the pattern as indicated by the fact that it is read out from pattern dictionary. Input part has columns for first, second, third and fourth extraction indication information shown in FIG. 19(a), (b), (c) and (d) together with the column for instruction information. The pattern P-2 shown in FIG. 6(b) is that of transitive verb with one object and the Table 2 of production rule for the pattern is huge table having entry for each verb or, furthermore, having entry for each condition of NP (noun phrase) at the right of verb which is kept unaltered. Here the part of the table covering tree structure in FIG. 18 and the verb "kiss" for reference purposes are expressed. Similarly with Table 1, columns for target language pattern are not filled with the letters P'-2-1 or P'-2-2 but with tree structure themselves represented by these letters. Figures for P'-2-1 and P'-2-2 are shown in FIGS. 20(a) and (b) and FIGS. 21(a) and (b). Target language pattern is consisted with, as in FIGS.
8(a) and (b), body of target language pattern shown in the (a) side of respective figure and structure order correspondence table which shows the correspondence of specific node in source language pattern and specific node in target language pattern. The correspondence table is the correspondence table between nodes in source language pattern and nodes in target language pattern which have empty columns to be filled with node number and nodes, on the other hand, which are newly introduced and do not need node number are ignored here. The node names with primes denote that they are in target language tree structure. As formerly explained, S', NP' and VT' denote sentence, noun phrase and transitive verb respectively. Among the nodes newly introduced, J' and JD' denote auxiliarly term and auxiliarly verb respectively. As shown in FIGS. 20(a) and (b), target language patterns include "wa", "o", "ni" and "masu" which are terminal node symbols. Above was minute description of memorized contents of pattern memorizing part MPM especially focusing on memorized contents of extraction indication memorizing region MER shown in FIG. 19 and production rule memorizing region PRT shown in Table 2, when pattern P-2 is taken as an example, and succcessively the operation of extraction generating part EXG and output deciding part SDS using above mentioned information, will be explained.
Tree structure in FIG. 18 from tree structure memorizing part IET and first, second, third and fourth extraction indication information shown in FIGS. 19(a), (b), (c) and (d) respectively from extraction indication memorizing region MER come in extraction generating part EXG. At EXG piling up of each term of IET output and MER output is conducted taking into account arbitrarizing measures and inspection measures A.sub.o, A.sup.o, E.sub.o, E.sup.o. The piling up with each structure in FIGS.
19(a), (c) and (d) fails and *'s are generated as the first, third and fourth extraction information. "play" from the E.sup.o under VT in FIG. 19(b) and "NMI" from the E.sup.o under NP right of VT emerge as second extraction information resulting in second extraction information of play.hoarfrost.NMI. .hoarfrost. denotes space symbol. Space is inserted among information emerged from different position. Second extraction indication information can be re-divided resulting in the situation where "play" and NMI emerge separately. Production rule shown in Table 2 from production rule memorizing region PRT and instruction from separating part IHP which is of no instruction at present, come in output deciding part SDS as shown in FIG. 7. From extraction generating part EXG, the information of play.hoarfrost.NMI is sent. The output deciding part SDS does operation of table look up of Table 2 and decides that input corresponds to the highest line with meaninful letters in the Table 2, as a consequence, sends target language pattern P'-2-1 to output tree structure memorizing part SPM and also sends "hiki(VT)" which is instruction to lower layer to instruction memorizing part INM. Extraction indication information except one in FIG. 19(b) are ones to cope with possible shape of noun phrase other than the shape of determinative+noun such as "the piano". They are noun itself like "I" or adjective+noun like "good piano" or determinative+adjective+noun like "the good piano". Three lines of information in Table 2 are, as explained later minutely, necessitated corresponding the fact that the verb "play" in English must be translated to be "hiki" when object is name of musical instrument (with category name of NMI) and translated to be "suru" when object is name of sports (with category name of NSP) and finally translated to be "enjiru" when the object is noun having the nature of a role (with category name of NRO). When verb happens to be "kiss", different treatment according to object becomes unnecessary and, as a result, the information in the column of second extraction information becomes "kiss.hoarfrost.-" involving the mark "-" of arbitrariness or of no information. Nevertheless, the object pattern here must be the one in FIG.
21(a) which requires auxiliary term "ni" after object NP' instead of the one in FIG. 20(a) at the case of "play".
The interesting way of use of A.sub.o, where a node or nodes with definite name is surrounded between A.sub.o 's. FIG. 22 is the example for the case where "play" will be generated when applied to the tree structure in FIG. 18.
Node number affixing part NMP receives tree structure in FIG. 18 from tree structure memorizing part IET and tree structure in FIG. 6(b) from pattern memorizing region MPR, detecting partial pattern with node number shown in FIG. 23. Node number processing part NNH generates the structure of FIG. 24 in which node numbers in source language are arranged according to structure order in source language tree structure using the structure of FIG. 23. Node number arranging part NNA generates the structure in FIG. 25 interchanging third and fourth node numbers in FIG. 24 according to structure order correspondence table in FIG. 20(b), using NNH output shown in FIG. 24 and structure in FIG. 20(b) which is output of output tree structure memorizing part SPM. This is the arrangement of node in the order of structure order in target language pattern tree structure. NNA output thus obtained is used to fill the empty column corresponding each node at target language pattern tree structure shown in FIG. 20(a) which constitute part of SPM output, giving rise to target language tree structure with node number shown in FIG. 26 at the output of output tree structure generating part SPG. The nodes newly generated at target language structure have no node number but it does not cause any inconvenience because these nodes will not be connected with any other part. The SPG output is introduced to output tree structure affixing part SPA and memorized there coexisting with former memory contents of output tree structure group memorizing part PGM shown in FIG. 12. Consequently new contents of memory of PGM will be the structure where the structure of FIG. 26 exists at the right side of the structure in FIG. 12.
In structure to lower layer consisting the other part of the output of output deciding part SDS is expressed in simplified fashion in Table 2 as "hiki(VT)" but actually this is meant to indicate that instruction of "hiki" must be given to VT node and nothing must be given to border nodes consisted of the other 2 NP's and is of the shape of structure in FIG. 27 resembling to FIG. 13. This information, after being memorized at instruction memorizing part INM, is introduced to instruction affixing part INA together with structure in FIG. 18 which is output of tree structure memorizing part IET. There, the operation of piling up is done among them and tree structure in FIG. 28 is generated. The output is introduced to erasing part, where erasing of the present pattern shown in FIG. 6(b) is conducted by erasing nodes higher than the nodes having instruction to lower layer, excluding ones on the border. As a result, 3 tree structures shown in FIG. 29 are sent to rest tree structure memorizing part RTM. This output is added with output of not handled tree structure memorizing part NHM at tree structure affixing part HTA. Tree structure affixing part HTA affixes tree structure in FIG. 17 at the right side of 3 trees in FIG. 26 ordered in this order and sends the result to present tree structure memorizing part CTM. Above is the operation of this system at the second round or the operation for pattern of P-2.
Following is the description of the operation of third round for the system in FIG. 7. The leftest tree structure in FIG. 29 or the tree structure of FIG. 30 is designated as handled tree structure at the handled tree structure deciding part HTD and sent to handled tree structure memorizing part HTM, and consequently other part of the input to HTD or the part in FIG. 31 is sent to not handled tree structure memorizing part NHM and memorized there. Tree structure of the shape of FIG. 30 out of HTM is separated into instruction and body of tree structure at the separating part IHP. The instruction information of no instruction is sent to output deciding part SDS, meanwhile the tree structure shown in FIG. 32 is sent to tree structure memorizing part IET. The IET output of the shape of FIG. 32 is sent to partial pattern finding part PPD, where the coincidence detection is done between pattern dictionary PTD. Present PPD output is pattern P-4 shown in FIG. 6(d), and the information of this selection is sent to pattern memorizing part MPM. MPM obtains information pattern P-4 from the information and pattern dictionary PTD and memorizes it in the 3 memorizing regions in MPM. Pattern memorizing region MPR stores structure of FIG.
6(d) unaltered, and extraction indication memorizing region MER stores the information of no information and finally production rule memorizing region PRT memorizes production rule shown in Table 3.
TABLE 3 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ -- -- P'-4-1 -- ______________________________________
Extraction generating part EXG sends information of no information to output deciding part SDS as there is no indication from extraction indication memorizing region MER. SDS sends the structure of P'-4-1 shown in FIG. 33 to output tree structure memorizing part SPM and also information of no information which is shown in FIG. 34 to instruction memorizing part INM according to the PRT output which is in Table 3, because of the fact that information of no instruction has arrived from separating part IHP. Further, only output of respective parts according to the order of processing will be mentioned. Node number affixing part NMP output is shown in FIG. 35 and node number processing part NNH output is shown in FIG. 36 and node number arranging part NNA output is shown in FIG. 37. Output tree structure generating part SPG output which is shown in FIG. 38 is added to output tree structure group memorized in output tree structure memorizing part PGM at the output tree structure affixing part SPA resulting in the tree structures in FIG. 39 with the same order of arrangement. Instruction affixing part INA output is shown in FIG. 40 and output of MPE or RTM is shown in FIG. 41. This is added to the left of the memory contents of not handled tree structure memorizing part NHM depicted in FIG. 31 at the tree structure affixing part HTA and the result is sent to present tree structure memorizing part CTM. The output is sent to handled tree structure deciding part HTD where the leftest tree structure shown in FIG. 41 is chosen as the handled tree structure and tree structure of FIG. 31 is again sent to not handled tree structure memorizing part NHM and memorized there. Output of handled tree structure memorizing part HTM in FIG. 41 is introduced to separating part IHP. The output of IHP is consisted of two parts and one of them which is information of no instruction is sent to output deciding part SDS and the other of them which is body of tree structure shown in FIG. 42
is memorized at tree structure memorizing part IET. Part of IET output is sent to partial pattern finding part PPD, where coincidence test by piling up with memory contents of pattern dictionary is performed resulting the information that P-I in FIG.
6(e) is chosen, which information is immediately sent to pattern memorizing part MPM. MPM, on the other hand, memorizes in its three regions the information concerning P-I using the information and information for P-I written in pattern dictionary PTD. Pattern memorizing region, among them, memorizes structure of FIG. 6(e) unaltered and extraction indication memorizing region MER stores the information of no information and production rule memorizing region PRT have production rule shown in Table 4.
TABLE 4 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ -- -- P'-I-1 -- ______________________________________
Extraction generating part EXG sends information of no information to output deciding part SDS as there is no indication from extraction indication memorizing region MER. Here, the information of no instruction has already come from separating part and so SDS, according to the production rule information in Table 2 which is PRT output, sends instruction of P'-I-1 in FIG. 43 to output three structure memorizing part SPM and also sends structure of FIG. 44 corresponding to no instruction to instruction memorizing part INM. Output of each part will be solely described hereafter according to the order of processing. Output of node number affixing part NMP is shown in FIG. 45 and output of node number processing part NNH is shown in FIG. 46
and output of node number arranging part NNA is shown in FIG. 47. The output of output tree structure generating part SPG is shown in FIG. 48, which is added to output tree structure group already memorized in output tree structure group memorizing part. Tree structure group memorized in PGM takes a shape consisted of that of FIG. 39 added with tree structure of FIG. 48 to the right. Output of instruction affixing part INA is shown in FIG. 49 and output of MPE or RTM is that of no output. As RTM output is that of no output, output of tree structure affixing part HTA becomes to be the same as output of not handled tree structure memorizing part NHM. HTA output is sent to handled tree structure deciding part HTD via present tree structure memorizing part CTM. Here again the leftest tree structure shown in FIG. 50 is selected as handled tree structure and is sent to handled tree structure memorizing part HTM and the rest of the tree structure shown in FIG. 51 is sent to not handled tree structure memorizing part NHM and memorized there. The output of handled tree structure memorizing part HTM shown in FIG. 50 is introduced to separating part IHP. IHP output consists of two parts and one of them, the information of "hiki" is sent to output deciding part SDS and the other of them, the body of tree structure depicted in FIG. 52, is memorized at tree structure memorizing part IET. The latter is then sent to partial pattern finding part PPD, where it is imposed with coincidence by piling up with memory contents of pattern dictionary PTD sending the information that P-play in FIG. 6(f) is selected to pattern memorizing part MPM. MPM, on the other hand, stores information concerning P-play in its three memorizing regions, where the information and information from pattern dictionary concerning P-play are used. Structure of FIG. 6(f) is memorized at the pattern memorizing region MPR unaltered, and the information of no instruction is memorized at extraction indication memorizing region MER and production rule shown in Table 5 enters at production rule memorizing region PRT.
TABLE 5 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ hiki -- P'-play-1 -- si -- P'-play-2 -- enji -- P'-play-3 -- ______________________________________
Extraction generation part EXG, obtaining no indication from extraction indication memorizing region MER, sends information of no information to output deciding part SDS. SDS decides that an input consisted of highest line in production rule expressed by Table 5 has come in, through the aid of the instruction "hiki" from separating part IHP and above mentioned information of no extraction, and consequently sends target language pattern P'-play-1 and information of no instruction to lower layer to tree structure memorizing part SPM and instruction memorizing part INM respectively. FIGS. 53(a), (b) and (c) show actual contents of P'-play-1, P'-play-2 and P'-play-3 respectively. For reference purposes, production rule where the verb "kiss" is used instead of the verb "play" is shown in Table 6 and related source language pattern of "kiss" and target language patterns corresponding figures in FIG. 53 are shown in FIGS. 54(a) and (b) respectively.
TABLE 6 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ hiki -- P'-kiss-1 -- ______________________________________
This corresponds to the description given in lower part of Table 2 and structure in FIG. 21(I a). Instruction was given in the shape of Table 2 and FIG. 27, for the case of pattern P-2, and on the other hand it is received in the shape of Table
5 and FIG. 53(a), for the case of P-play, which instruction is used in selection of translated word for "play". The aim of use of instruction, other than the use for selecting translated words shown here, can turn out to be the use for tranformation of negative source language pattern to affirmative target language pattern and the use of transformation of future tense to present tense and various other uses conforming to various requests in natural language. As seen in the tables mentioned so far, the transformation can be expressed by production rules which generate pairs consisting of target language pattern and instruction to lower layer by the use of instruction from upper layer and extraction information from lower layer. This is the merit of production rule which constitutes important element in this invention. The type of instruction can be arbitrary as far as it is registered at the patterns in lower layer. Node number affixing part NMP generates again the structure in FIG. 52 to its output through the use of tree structure in FIG. 52 from tree structure memorizing part IET and tree structure in FIG. 6(f) from pattern memorizing region MPR. Based on NNH output shown in FIG. 55 and right side part of the structure in FIG. 53(a) which is output of output structure memorizing part SPM, node number arranging part NNA generates the structure consisting of node numbers arranged in the order of structure order in target language tree structure and, as a result and by the use of above information, the tree structure shown in the left side of FIG. 53(a) which is a part of SPM output, sends the target language structure with node number shown in FIG. 56 as its output. This output is introduced to output tree structure affixing part SPA, where it is affixed to the right of the memory contents in output tree structure group memorizing part PGM. As a result, memory contents of output tree structure group memorizing part PGM become the one shown in FIG. 57. Instruction memorizing part INM, as is formerly seen, is generating the information of no instruction shown in FIG. 58. The information and tree structure memorizing part IET output aid to generate the output shown in FIG. 59 at the instruction affixing part INA. This enters in erasing part MPE making the output of MPE to be no output, in consequence of the fact that output of rest tree structure memorizing part is also of no output. Only not handled tree structure memorizing part NHM output enters to tree structure affixing part HTA, because RTA sends no output. This information enters into present tree structure memorizing part CTM via handled tree structure deciding part HTD. HTD emits the structure expressed in FIG. 60 to handled tree structure memorizing part HTM and also emtis the structure in FIG. 61 to not handled tree structure memorizing part NHM. The processing in the system of this invention progresses similarly as before but the operation of the circular part, from now on, is abbreviated at the explanation and the result will be only expressed in the following passage because recognition for the operation becomes easy as there is no instruction operation hereafter. Ultimately tree structure group in FIG. 62 becomes memorized at the output tree structure group memorizing part PGM after the operation of circular part so far explained. At the figure, the contents of upper left column, upper right column and lower left column are memorized in this order. The source language patterns P-3, P-the, P-piano and P-period are shown in FIGS. 6(c), (g), (h) and (i) respectively and corresponding production rules are shown in Table 7, 8, 9 and 10 respectively and also corresponding target language patterns which are P'-3-1, P'-the-1, P'-piano-1 and P'-period-1 are expressed by FIGS. 63, 64, 65 and 66 respectively, which give rise to the target language tree structures with node numbers shown in the fourth, third, second and first portion in FIG. 62 counted from right respectively. Here, DET' and NMI' denote node marks for determinative and musical instrument name in target language respectively.
TABLE 7 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ -- -- P'-3-1 -- ______________________________________
TABLE 8 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ hiki -- P'-the-1 -- ______________________________________
TABLE 9 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ hiki -- P'-piano-1 -- ______________________________________
TABLE 10 ______________________________________ Input Output Instruction Target Instruction from upper Extraction language to lower layer information pattern layer ______________________________________ hiki -- P'-period-1 -- ______________________________________
Above is the explanation concerning circular part of the system in FIG. 7. At the last stage of the circulation the situation where input to handled tree structure memorizing part HTM is absent, occurs. The information, namely information of end of circulation, is sent to output tree structure connecting part SPC and target language pattern linearizing part SPL, resulting in commence of operation at these parts. First SPC repeats the operation in which "second from leftest" tree structure in the tree structure group memorized in work memory region in SPC is merged with the leftest one at the node common to both using structure in FIG. 62 emerged from output tree structure group memorizing part PGM, and finally generates one tree structure. The result of first merge, the remaining part after the first merge and final result of merge are shown in FIGS. 67, 68 and 69 respectively. The structure in FIG. 69 is output of output tree structure connecting part SPC, which is introduced to target language pattern linearizing part SPL. SPL picks up terminal nodes from input tree structure shown in FIG. 69 and removes node numbers from them and finally arranges them at the order of original position in FIG. 69 resulting in the output of FIG. 70 and generates the information keeping the order unaltered and finally gives the target language sentence or translated result in Japanese. The result is:
This in the output corresponding to the input tree structure shown in FIG. 4. When verb is altered from "play" to "kiss" at the FIG. 4, the result obtained via the structure of FIG. 21(a) becomes:
Here operation of parts comprising the system of this invention shown in FIG. 7 must be reviewed again to make clear the operation as a whole. Explanation is successively made for every part except for simply constituted memorizing parts. The typical operation of handled tree structure memorizing part HTD will be as follows. Namely, it selects leftest one from tree structure group shown in FIG. 29 as handled tree structure and sends to handled tree structure memorizing part HTM and sends remaining parts or tree structure group in FIG. 31 to not handled tree structure memorizing part NHM and, as a result, separates leftest tree structure and other part among tree structure group constituted of many tree structures. When the input is constituted of only one tree structure as is in FIG. 4, the input becomes its output unchanged.
Separating part IHP takes tree structure with instruction at the highest node as shown in FIG. 50 as an input and generates instruction information and body of tree structure shown in FIG. 52 in separated fashion, where instruction information is sent to output deciding part SDS and body of tree structure is sent to tree structure memorizing part IET. When instruction attached to the highest node is mark of "-" of no information, IHP sends information of no information to SDS. Partial pattern finding part PPD, taking tree structure memorizing part IET output as one input and taking pattern dictionary PTD output as the other input, calls up each term registered in PTD successively and compares it with IET output and trys to find a tree structure which is partial tree structure of IET output and which, moreover, contains the highest node of IET output as its highest node. When the tree structure memorizing part IET output happens to be as shown in FIG. 18, as explained minutely concerning FIG. 18, registered term of FIG. 6(b) in pattern dictionary is chosen.
Pattern memorizing part MPM obtains information concerning the name of coincident partial pattern from partial pattern finding part PPD together with information of formerly mentioned coincident partial pattern written in PTD from PTD and memorizes this information in the three memorizing regions in MPM. When information is attached to above mentioned pattern, the signal path from PTD to PPD becomes unnecessary. Above-mentioned information consists of three parts which are coincident partial pattern, extraction indication information and production rule and these are memorized in pattern memorizing region MPR, extraction indication memorizing region MER and production rule memorizing region PRT respectively. When the coincident partial pattern is as shown in FIG. 6(b), for example, memory contents in MPR is of course as shown in FIG. 6(b) and memory contents in MER is four tree structures in FIG. 19 and memory contents of PRT is as shown in Table 2. Explanation for FIG. 19 is made at the explanation of extraction generating part EXG and that of Table 2 is made at the part of output deciding part SDS.
Extraction generating part EXG obtains information by piling up some tree structure terms contained in extraction indication memorizing region MER on tree structure memorized in tree structure memorizing part IET. Each tree structure term in MER has the structure of coincident partial pattern but attached with some additional structure. To the tree structure terms the arbitrarization measures which ensure that the parts affected by the measures must not pile up with the tested tree and can be arbitrary and inspection measure which directs to inspect some portion or the whole of the parts affected by arbitrarization measure, are also attached. The explanation is already done at FIG. 18 or FIG. 19.
Output deciding part SDS, using production rule related to the coincident partial pattern sent from production rule memorizing region PRT and obtaining information of instruction from upper layer which is one of the input required by above-mentioned production rule, from output of separating part IHP and also obtaining extraction information which is the other of the input, from above-mentioned extraction generating part EXG, generates output consisting of two sorts of information which are target language pattern and instruction to lower layer. The operation of this part is done by the shape of table look up which consists of finding pair of input which falls under desired one and generating corresponding output. At the example of FIG. 20, target language pattern consists of body of target language pattern shown in FIG. 20(a) and structure order correspondence table which is a correspondence table between the structure order of source language nodes shown in FIG. 20(b) and that of target language nodes, and both of them are sent to output tree structure memorizing part SPM. The other part of SDS output is instruction to lower layer, which consists of coincident partial pattern tree structure but attached with instruction to lower layer at border nodes and which is sent to instruction affixing part INA via instruction memorizing part INM. When no instruction must be sent, the marks of no instruction which are "-" are attached to the border nodes. The information, at the example of P-2 is shown in FIG. 27. Node number affixing part NMP receives input concerning whole tree structure presently treated, from tree structure memorizing part IET and also receives input concerning coincident partial pattern deprived of node numbers from pattern memorizing region MPR, and piles up the former on the latter and takes off the portion of the former not involved in the latter and generates as a result coincident partial pattern with node numbers. As for example of pattern P-2, the processing corresponds to the generation of output of FIG. 23 from the two portions of information which are shown in FIG. 18 and FIG. 6(b).
Node number processing part NNH does the operation of arranging node numbers according to structure order using the input consisting of node number affixing part NMP output. Similarly when the case of P-2 is taken as an example, this part generates output of structure in FIG. 24 using the input tree structure shown in FIG. 23. Node number arranging part NNA receives structure order corresponding table which is correspondence table between nodes in source language pattern and target language pattern emerged from output tree structure memorizing part SPM, and also receives the structure made of a row of node numbers arranged according to structure order of source language and generates the structure made of a row of node numbers arranged according to structure order of target language. As for the example of pattern P-2, the processing corresponds to the generation of the structure in FIG. 25 using the structure in FIG. 24 and that in FIG. 20(b).
Output tree structure generating part SPG uses node number arranging part NNA output which is row of node number arranged in structure order and also uses target language pattern structure with empty column, both as input information, and does operation to fill empty columns in above-mentioned pattern with node numbers in corresponding structure order. In the example P-2, the operation is to generate structure in FIG. 26 from structure of FIG. 20(a) which is output of output tree structure memorizing part SPM and structure of FIG. 25 which is output of node number processing part NNH.
A portion of instruction affixing part INA input is tree structure memorizing part IET output which is, an INA, piled up with coincident partial pattern tree structure having instruction to lower layer at border nodes and consisting the output of instruction memorizing part INM. INA transposes, as a result, instruction to lower layer formerly obtained by the border nodes of the latter to the corresponding nodes in the former tree structure. For the case of pattern P-2, it corresponds to the operation of piling up the structure in FIG. 18 on the structure in FIG. 27 and giving rise to the structure in FIG. 28.
Erasing part MPE, as formerly mentioned, erases all nodes higher than the nodes with instruction to lower layer from the formerly mentioned instruction affixing part INA output. As for the case of pattern P-2 the operation corresponds to generation of structure of FIG. 29 from that of FIG. 28.
The structure affixing part HTA adds output of not handled tree structure memorizing part NHM to the right of the output of rest tree structure memorizing part RTM. Similarly output tree structure affixing part SPA adds output of output tree structure generating part SPG to the right of output tree structure generating part SPG output. As the operation of output tree structure connecting part SPC and target language pattern linearizing part SPL will not be treated here whereas they have been explained minutely.
Above is explanation for the system in FIG. 7 including detailed explanation for every composing part. These composing parts can be realized by ample program of list processing computer language called LISP using programs which indicate modification, addition, elimination and test of coincidence of tree structure written by the language. The system also can be realized by some high grade computer language such as PL-1 without using LISP. Composing parts of the system of this invention shown in FIG. 7 can be also realized by electronic circuit without using above-mentioned computer languages. The methods of the realization is mentioned hereafter for every composing part in FIG. 7.
For the case, the expression of a tree structure by a row of letters must be used. The expression is called as expression by S equation. This expression is based on the expressing method of Eq. (13) for the structure where some children nodes are connected directly below a mother node.
At the above equation, the part written between the left parenthesis "("and right parentheses ")" is expressed to be connected directly below the node written directly left of the left parenthesis. Children nodes are arranged in the same order as in the order in corresponding tree but separated by blank marks ".hoarfrost.". Using this method the structure in FIG. 6(a) is written as:
and the example of FIG. 3 which is a little complicated can be expressed as is in the following Eq. (15) successively using the expression shown in Eq. (13).
The expressions not included in ordinary S equation, where node number is expressed by the number surrounded by large parentheses [] at the directly right position to the corresponding node and instruction is expressed by the instruction surrounded by angle parentheses <> at the left to correspond node, are introduced here. For example the structure of FIG. 30 is expressed as:
The empty node number position is expressed by left large parentheses "[" and the case of FIG. 20(a) for example is expressed as:
A.sub.o, A.sup.o, E.sub.o and E.sup.o corresponding to arbitrarization measures and inspection measures are expressed as they are ordinary nodes. For example the structure in FIG. 19(b) can be written as:
The structure in which some tree structures are arranged in a row, is expressed by the row of sequences consisting of S equation each of which corresponds to a tree structure, with more than one spaces between sequences. For the sake of clarity at description, a bar is inserted at the space between sequences of tree structures in this explanation as shown in Eq. (19) corresponding to FIG. 31, but in the actual processing in this invention, there are no such bars at the position of above-mentioned spaces. ##EQU1##
Above is the explanation concerning S equation used in the invention and following is composing component in the system of machine translation in FIG. 7 using above-mentioned expression of tree structure. The input to the machine translation of this invention is the result of pre-processing expressed in S equation explained in Eq. (13). The input tree structure in FIG. 4, for example, is expressed by: ##EQU2## Following the operation of composing elements of machine translation system shown in FIG. 7.
Input tree structure memorizing part ITM can be composed by ordinary RAM (random access memory), and so explanation for the detail of this part is abbreviated. The situation is the same for present tree structure memorizing part CTM. Typical operation of handled tree structure deciding part HTD is one, in which the tree structure shown in FIG. 30 which is the leftest among the structure in FIG. 29 is selected as handled tree and sent to handled tree structures memorizing part HTM and the other component consisting of tree structure group shown in FIG. 31 is sent to not handled tree structure memorizing part NHM. The S equation expression for above operation is the operation of receiving the structure in following Eq. (21) and sending the structure in following Eq. (22) which is the leftest to HTM and sending other component to NHM. ##EQU3##
It will be easily seen that number of left parentheses and right parentheses contained in a tree structure are equal. Handled tree structure deciding part HTD can be realized by the electronic circuit shown in FIG. 71. AMT, CTP and CLC, in FIG.
71, are start pulse input terminal, present tree structure input terminal receiving signal from present tree structure memorizing part CTM and clock input terminal respectively and they constitute the entire input terminals in handled tree structure deciding part HTD. HHT, HNT and HST are handled tree structure output terminal sending signal to handled tree structure memorizing part HTM, not handled tree structure output terminal sending signal to not handled tree structure memorizing part NHM and completion pulse output terminal sending the information that the operation of handled tree structure deciding part HTD is completed. They all constitute the entire output terminals of HTD.
HTA, HTB and HTC are A, B and C shift registers respectively and clock terminal of these shift registers are HAL, HBL and HCL respectively. B shift register HTB and C shift register HTC have input terminals HBT and HCT respectively. Input terminals will be written at the input terminal of rightest stage of shift register through the figures appearing hereafter, except commented otherwise. A shift register HTA has two output terminals HT1 and HT2 and they are called A shift register first output terminal and A shift register second output terminal respectively. Hereafter except the case where other notation is indicated, the output terminal of leftest stage of shift register has a name with 1 at the last letter and the output terminal of the stage of the stage right of the former stage has a name with 2 at the last letter. The output terminal having 1 at the last letter of its name and having 2 at the last letter of its name are called first ouput terminal and second output terminal respectively. Similarly the way of expression is applied to numbers other than 1 and 2. Simultaneous input and simultaneous output to and from the whole stages of the A shift register HTA is possible. The symble of shows the path of simultaneous input and consequently the lead connected to the symbol is of multi-leads and deals with multi-signal. The symbol of shows similarly the symbol for simultaneous output at whole stages. Accordingly, B shift register HTB and C shift register HTC can conduct simultaneous input and output operation. All registers do the operation of sending signal by one stage to the left every time clock signal comes at their clock terminals. Shift register having these functions can be realized by RAM (random access memory). Every shift register consists of 1 bit shift registers arranged in parallel configuration enough to accommodate all of letters used in natural language together with parentheses (), angle parenthese < >, large parenthese [ ] used for processing and also A.sub.o, A.sup.o, E.sub.o, E.sup.o which are symbols for dealing condition.
AND in the figure is AND circuit which emits 1 at its output when all of its input signals are 1 and emits 0 otherwise. OR in the figure is OR circuit which emits 0 at its output when all of its input signals are 0 and emits 1 otherwise. They are realized by gate circuits. SPD is space detector and LPD is left parentheses detector and RPD is right parenthesis detector all of which emit 1 when letters which must be detected by these specific detectors occur at their input consisting of some bits and emit 0 otherwise. The circuit doing above-mentioned operation can be realized by keeping a bit input which must be 1 at the letter to be detected, unchanged and inverting, by an inverter which generates 1 at the output when the output is 0, a bit which must be 0 and then introducing all input to an AND circuit. SPG is space detector group which consists of a plurality of space detectors of the number equal to the stage number of A shift register HTA and do simultaneous input and output operation explained by symbols of . The part denoted by INV is inverter which emits 1 when input is 0 and 0 when input is 1 and can be realized by gate circuit.
HFA is A state flip-flop and HFB is B state flip-flop and HFC is C state flip-flop. These flip-flops play the role of memorizing the operating state of this part HTD. For example when this part is at the state of S.sub.A, A state flip-flop is "on" and emits 1 and other flip-flops are "off" and emit 0. Of course when this part is at the state of S.sub.B, B state flip-flop HFB becomes "on" and others are "off". Hereafter the notation that "x" state flip-flop which has letter "x" at the last of its name, is "on" when the part is at state S.sub.X, is used. Hereafter the expression where the upper terminal among the two terminals of each flip-flop is "on" terminal and the flip-flop becomes "on" and begins to emit 1 as its output when this terminal receives a pulse and the lower terminal is "off" terminal and flip-flop becomes "off" begins to emit 0 as its output when this terminal receives a pulse.
UDC is up-down counter which count-ups by one count when a pulse appears on the upper terminal among its two input terminals and count-downs by one count when a pulse appears on the lower terminal. Hereafter the notation is observed. UDT is unit detector which emits 1 when count of up-down counter is 1 and otherwide emits 0.
Here the explanation for composing parts as themselves in handled tree structure deciding part HTD shown in FIG. 71 is concluded and the part of nature which is common to FIG. 73 or the figures after FIG. 73 is abbreviated to avoid complexity.
Following is the operation of the handled tree structure deciding part HTD as a whole, the operation of HTD will be summarized as follows. It reads-in S equation of the type of Eq. (21), for example, in its A shift register HTA and moves S equation of Eq. (22) which corresponds to handled tree structure to B shift register HTB and moves other parts to C shift register HTC. The detailed is given below.
The part or handled tree structure deciding part HTD has a state diagram of FIG. 72. Namely this part has four states consisting of S.sub.0, S.sub.A, S.sub.B and S.sub.C. The state transition signals are C.sub.0A, C.sub.AB, C.sub.BC and C.sub.C0. State are, as before, expressed by S followed by a suffix hereafter and state transition signals are expressed by C followed by suffixes. As seen in FIG. 72 the states progress in one direction and finally come back to S.sub.0. Explanation is made for the nature of each state. The state S.sub.0 is idling state of this part where all flip-flops HFA, HFB and HFC are in "off" condition sending no output and interrupting, through the effect of AND circuit, clock signal present continuously at the clock input terminal CLC and giving, as a result, no clock signal to shift registers HTA, HTB and HTC and preventing the operation of each register. The clock signal is supplied to every composing part including this part from single clock oscillator. The oscillator can be realized by ordinary pulse generator of constant oscillating frequency.
When this part is in the state S.sub.0, which is the initial state of this part, the pulse reporting that present tree structure memorizing part CTM which is situated in front of this part has completed its operation, comes in as the start pulse to this part at start pulse input terminal AMT. Then the part transfers to state S.sub.A by making A state flip-flop HFA "on". Namely, start pulse at AMT constitutes state transition signal C.sub.0A. Further, as is apparent in FIG. 71, the present tree structure information written in Eq. (21), for example, is read-in in parallel fashion in A shift register HTA through present tree structure input terminal CTP which receives signal from present tree structure memorizing part CTM and through AND circuit connects to the CTP. The fact that AND circuit plays the roll of switch is easily recognized considering that letters are transferred in the shape divided to their composing bits. State S.sub.A following C.sub.0A is the state when clock pulse is fed to clock terminal HAL of A shift register HTA through the AND circuit directly right of A state flip-flop HTA, resulting that HTA continuously transfers its memory contents by on memory stage every time clock signal arrives. B shift register HTB and C shift register HTC are in idle condition whereas no clock signal is fed to them. During these operations the instance comes when left edge of meaningful part of memory contents, which is any letter other than the letter "space", of HTA comes on the second output terminal. Then signal other than space appears, for the first time, at the output terminal which has been continuously emitting space signal. At this instance the output of 1 appears at the output terminal of invertor INV which receives output of space detector SPD and the signal makes, as seen in FIG. 71, A state flip-flop HFA "off" and also makes B state flip-flop "on". Apparently the state transition signal C.sub.AB in FIG. 72 corresponds to first letter other than space at the terminal of HT2. The aim of AND circuit on the path of signal which makes HFB "on" HFA "off" is to prevent error of operation by making information other than space constituting state transition signal C.sub.AB effective only at the state of S.sub.A and also making above information ineffective in states other than S.sub.A. These types of error preventing measures are utilized all over the composing component in FIG. 7. C.sub.AB transfers the states from S.sub.A to S.sub.B. At the state of S.sub.B only B state flip-flop HFB is "on" resulting in the situation that clock signal is fed to A shift register and B shift register through their clock terminals HAL and HBL respectively and that B shift register begins to read-in signal from first output terminal HT1 of A shift register through its input terminal HBT. As reading-in of signal at each shift register begins at the arrival of first clock signal arriving after the transition, the point of gathering of information telling the appearance of signal other than space, is chosen to the second output terminal HT2 and not first output terminal HT1 of A shift register HTA to prevent drop-out of signal. The state S.sub.B is the one where signal from A shift register comes into B shift register which memorizes handled tree structure. At the state S.sub.B, left parenthesis detector LPD, right parenthesis detector RPD, up-down counter UDC and unit detector UDT as a whole are counting number of parentheses, appearing at the first output terminal HT1 of A shift register, doing the operation of counting-up when left parenthesis "(" appears and counting-down when right parenthesis ")" appears. UDT emits 1 when left parenthesis "(" has been counted by one count more than right parenthesis ")". When right parenthesis ")" and space appear at first output terminal HT1 of A shift register and second output terminal HT2 respectively during the period when UDC is emitting 1, B state flip-flop HFB is made "off" and C state flip-flop HFC is made "on" through the operation of space detector SPD and right parenthesis detector RPD and succeeding AND circuit shown in FIG. 71. As a result state is tranferred from S.sub.B to S.sub.C. Namely the state transition signal C.sub.BC in FIG. 72
corresponds to the condition where right parenthesis, space and 1 are appearing at HT1, HT2 and output terminal of up-down counter UDC.
At the state S.sub.C, clock is fed to A shift register HTA and C shift register HTC and HTA output is being read-in into HTC which is shift register for "not handled tree". The situation is easily recognized at FIG. 71. During above operation, the instance when all information in A shift register go out making HTA empty, comes. Then each output of composing part of space detector group SPG connected to corresponding stage in HTA becomes 1 making output of AND circuit following SPG also 1. This last signal makes C state flip-flop "off" and consequently makes all state flip-flops "off" changing states from S.sub.C to S.sub.0. The state transition signal C.sub.C0 is information of emptiness in A shift register HTA. The state S.sub.0 is the state when all composing part in FIG. 71 is in stop or idle condition. The signal corresponding to C.sub.C0 and making C state register "off" is sent to next components which are handled tree structure memorizing part HTM and not handled tree structure memorizing part NHM. At this timing, this part sends to outer circuits the information of handled tree structure memorized in B shift register HTB and the information of not handled tree structure through formerly mentioned handled tree structure output terminal HHT and not handled tree structure output terminal HNT respectively.
The description of treatment of Eq.(21) when Eq.(21) is input signal of this part or handled tree structure deciding part, is as follows. The row of letters in Eq.(22) expressing a tree structure is read-in in parallel fashion to A shift register HTA at the instance of transition of states from S.sub.0 to S.sub.A through the effect of C.sub.0A. The row of letters in Eq.(21) which is read-in, continuously traverses, during the states S.sub.A, S.sub.B and S.sub.C to the left in HTA every time clock pulse arrives and is erased from memory contents of HTA, through the leftest memory stage of HTA corresponding to first output terminal HT1 of HTA, by piecewise fashion from the leftest remaining letter. To explain the situation, letters in Eq.(21) with indication, under the letters, expressing the state of this handled tree structure deciding part HTD when corresponding letter is at the stage of HT1. The result is Eq.(23). ##EQU4## As output of A shift register HTA is accommodated in B shift register HTB during the state of S.sub.B, the component of letters in Eq.(23) corresponding to the indication of state S.sub.B enters in B shift register and finally sent to handled tree structure memorizing part HTM and the component corresponding to the indication of state S.sub.C enters to C shift register HTC and finally sent to not handled tree structure memorizing part NHM. As seen before, the effect of state transition in response to state transition signal does not appear until the next clock pulse after the state transition and accordingly the border of states are laid between state transition signal and next signal. Above explanation is for the operation of handled tree structure deciding part HTD.
Next the separating part IHP is dealt with. The typical operation of this part is expressed as follows. IHP obtains the tree structure in FIG. 50 from the output of handled tree structure memorizing part HTM and sends the instruction and handled tree structure deprived of instruction shown in FIG. 52 to output deciding part SDS and tree structure memorizing part IET respectively. When this part is realized by electronic circuit, input to separating part IHP, output to output deciding part SDS and output to tree structure memorizing part IET can be written as is Eq.(24), (25) and (26) respectively.
The circuit to do the operation has almost the same configuration with handled tree structure deciding part HTD and has also four states. The only difference consists of the fact that state transition signal C.sub.BC for the state transition from S.sub.B to S.sub.C becomes to be appearance of right angle parenthesis ">" at first output terminal HT1 of A shift register HTA instead of appearance of right parenthesis ")" and space at first output terminal HT1 and second output terminal HT2
respectively in the case of HTD. So the detailed explanation for this part is abbreviated. At the separating part IHP, the instruction output to output deciding part SDS is obtained from the part corresponding to B shift register HTB and output to tree structure memorizing part IET is obtained from the part corresponding to C shift register HTC.
Next the part of partial pattern finding part PPD is dealt with. FIG. 73 is the circuit for the part constituted by electronic circuit. PPD has four input terminals which are clock input terminal CLC, tree structure input terminal PPT receiving signal from tree structure memorizing part IET, pattern dictionary information input terminal PTT receiving information from pattern dictionary PTD and start pulse input terminal PST which receives start pulse telling that the operation of tree structure memorizing part IET has been completed and indicating the start of operation in this part of PPD. PPD has four output terminals. They are completion pulse output terminal SCT receiving completion pulse which expresses success of comparison and indicates reading-in of dictionary contents to pattern memorizing part MPM, dictionary contents output terminal PTS which sends out, unaltered, the signal coming in from pattern dictionary information input terminal PTT, help signal output terminal HLT which emits help signal to stop all the circuits in the mechanical translation system in FIG. 7 and requests intervention of man at the occasion of failure in finding comparison pattern and dictionary scanning information output terminal DST which emits, to pattern dictionary PTD, dictionary scanning information requesting the term next to the term emitted presently at pattern dictionary PTD.
As pattern dictionary PTD can be realized by, for example, shift registers or ROM's (read only memory) or magnetic tapes with apparatuses to memorize presently emitted output, the realization method is not explained here. The pattern dictionary PTD must be designed to give its output continuously to this part through pattern dictionary information input terminal PTT. PTD does also the operation of beginning to emit the term next to the term formerly emitted when output appears at the dictionary scanning information output terminal DST. At the end of registered terms in pattern dictionary PTD, plural of "z" which is the last letter of alphabet is written and when comparison is not concluded after scanning dictionary to this term, this part generates help signal at help signal output terminal HLT.
Following is description of composing elements in partial pattern finding part PPD concentrating on elements which have not been explained before. PPA and PPB are A shift register and B shift register respectively among which PPA memorizes output of pattern dictionary PTD and PPB memorizes output of tree structure memorizing part IET which is tree structure to be compared. PPA and PPB, as shown in FIG. 73, can read-in signals, simultaneously, to their all memorizing stages. Output terminal of PPA is first output terminal PA1 and output terminal of PPB are first output terminal PB1 and second output terminal PB2. Clock terminals of PPA and PPB are PAL and PBL respectively. AZD is A.sub.0 detector emitting 1 when it detects letter A.sub.0. LLD and RLD are left large parenthesis detector and right large parenthesis detector respectively and they generate 1 when corresponding letters are detected. CSD is coincidence detector which emits 1 when signals coming in to its two input terminals are identical. ZDG is z detector group consisting of a plurality of z detectors of the same number with the number of the stages in A shift register PPA. It operates in accordance with AND circuit which follows it and which emits 1 when output signals of all stages of PPA are z's. PFA, PFB, PFC, PFD and PFE are flip-flops corresponding to the states having names of the last letters in the name of above flip-flops. For example PFA is A state flip-flop. The condition when each of the flip-flops becomes "on" is explained formerly. This part has states S.sub.A, S.sub.B, S.sub.C, S.sub. D and S.sub.E corresponding to each state flip-flops and S.sub.0 corresponding to the condition in which all the flip-flops are "off". ZDT is 0
detector emitting 1 when up-down counter is counting 0. The terminal denoted by RST situated in up-down counter UDC is reset terminal receiving signal to reset the counter.
As the presentation of composing element in FIG. 73 is concluded, the explanation for the operation of partial pattern finding part PPD as a whole will be done next. The state diagram of PPD has the structure shown in FIG. 74. C.sub.0A is signal constituted with completion pulse showing the completion of operation in tree structure memorizing part IET, coming in as start pulse of this part, at the start pulse input terminal PST. At the instance of this pulse A state flip-flop PFA becomes "on", and moreover, dictionary contents and tree structure to be compared with are read-in through pattern dictionary information input terminal PTT and tree structure input terminal PPT respectively. These condition can be observed by FIG. 73.
As the operation is apparent from FIG. 73, only the results are presented now. C.sub.A0 occurs, as formerly explained, when all stages of A shift register emit z's and as a result help signal is generated at help signal output terminal HLT. C.sub.AB occurs when space is emitted at PB1 terminal in B shift register PPB. C.sub.AC occurs when, on the contrary, the letter other than space is generated. C.sub.BC occurs when a letter other than space comes at PB2 terminal of PPB. C.sub.CA occurs when output of PA1 terminal in A shift register PPA and that of PB1 terminal in B shift register PPB is inconsistent and output of PA1 terminal is not A.sub.0. At the occasion, output appears at dictionary scanning information output terminal DST and pattern dictionary PTD is directed to emit the next term and, moreover, re-reading-in of tree structure and reading-in of new dictionary term is conducted through tree structure input terminal PPT and pattern dictionary information input terminal PTT respectively. C.sub.CD is generated when left large parenthesis "[" occurs at PB2 terminal and C.sub.DC occurs when right large parentheses "]" is emitted at PB1 terminal. C.sub.CE is the case when A.sub.0 is generated at PA1 terminal and then up-down counter UDC is reset. C.sub.EC occurs when right parenthesis ")" occurs at PB2 terminal and also up-down counter is emitting 0. C.sub.C0 is the signal which is generated when A shift register PPA and B shift register PPB become empty telling the success of comparison. At this instance, this part emits completion pulse at completion pulse output terminal SCT.
Following is the operation of this partial pattern finding part PPD at each state. At states S.sub.A through S.sub.E, clock pulse is fed to clock terminal PBL of B shift register PPB making this shift register to shift its memory contents to the left by one memory stage every time clock signal arrives. Only at S.sub.C clock is fed to clock terminal PAL of A shift register PPA. S.sub.0 is, as mentioned before, idle state of this part. The operation of this part is expressed using an example. The typical operation of PPD is to decide, by piling-up, whether there is any partial pattern selected from terms in pattern dictionary PPD which coincides with output of tree structure memorizing part IET which is, by now, the tree structure in FIG. 18. Now, the case of piling up pattern P-2 shown in FIG. 6(b) to above mentioned tree, is considered. The S equation of the tree structure in FIG. 18 is as follows. ##EQU5## The tree structure expressing P-2 in FIG. 6(b), to be registered in pattern dictionary can be written by following Eq.(28) using aforementioned symbol for arbitrarization measures A.sub.o. ##EQU6## Of course Eq.(28) can be expressed by tree structure in FIG. 75. When start pulse or state transition signal C.sub.0A arrives at start pulse input terminal PST, the state of PPD is switched over from S.sub.0 to S.sub.A. At the case where memory contents of B shift register PPB is not "stuffed to the left" or contents does not begin at the first stage of the register, state transition signal C.sub.AB occurs immediately afterword and the state is transferred to state S.sub.B and B shift register PPB begins to shift its memory contents or row of letters shown in Eq.(27) to the left. At the explanation for later operation the description for state transition is almost omitted. The state changes over to S.sub.C when the left-most letter S in FIG. 27 arrives at PB2 terminal at B shift register PPB. At the instance when first clock pulse in state S.sub.C comes, the row of letters expressed in Eq.(27) is memorized in "stuffed to the left" fashion in consequence of the fact that memory contents including the letter S is shifted by one memory stage directly after the state transition. The dictionary registering method in which a term consisting of row of letters like the example of Eq.(28) can be memorized in A shift register PPA, at the occasion of simultaneous input to all stages in PPA, in "stuffed to the left" fashion, must be utilized. The state transfers to S.sub.D after the existence of S.sub.C by only one clock interval, as the consequence of the fact that a letter corresponding to left large parenthesis "[" next to S in Eq.(27) appears at PB2 terminal when first clock pulse after the state transition to S.sub.D comes. At the instance of first clock signal of state S, the part after and including left large parenthesis "[" next to S among the letters in Eq.(27) is memorized in B shift register PPB and the part after and including left parenthesis "(" next to S is memorized in A shift register PPA. During the duration of state S.sub.D in which only B shift register PPB continues to send its memory contents to the left, the instance in which right large parenthesis "]" which is fifth letter in Eq.(27) is generated at PB1 terminal switching the state back to state S.sub.C. From this instance on, both of registers PPA and PPB begin to send their memory contents to the left simultaneously. When left large parenthesis "[" which is ninth letter in Eq.(27) appears at PB2 terminal the state transfers to state S.sub.D and when right large parenthesis "]" which is thirteenth letter appears at PB1, the state comes back to state S.sub.C. At the instance when first clock signal of state S.sub.C of this round appears, the fifth letter in Eq.(28) and fourteenth letter in Eq.(27), both of which are left parentheses "(", are appearing at PA1 terminal and PB1 terminal respectively.
A.sub.o in Eq.(28) comes to PA1 terminal at the next clock pulse and state is transferred to state S.sub.E and up-down counter UDC is reset. The condition of occurrence of C.sub.EC where right parenthesis ")" comes when up-down counter UDC is counting 0 and 1 is generated at the output of 0 detector, is satisfied when right parenthesis ")" which is seventh letter in Eq.(28) appears at PA1 terminal and right parenthesis ")" which is thirty-second letter in Eq.(27) at PB1 terminal. At the instance of above occasion, state transfers to S.sub.C and both A and B shift registers begin to send their memory contents to the left simultaneously. The initial condition of above state is that first space in both of Eq.(27) and Eq.(28) are appearing at PA1 terminal and PB2 terminal respectively. As explained above, the pattern piling up with arbitrarization measures becomes possible by utilizing arbitrarization symbol A.sub.o. By continuing above operation, at the example, the piling up is successfully completed making both registers PPA and PPB empty and sending completion pulse which reports success of comparison, at completion pulse output terminal SCT.
Pattern memorizing part MPM situated "downstream" of this partial pattern finding part PPD, reads-in, at the instance of occurrence of this completion pulse, the output at dictionary contents output terminal PTS of PPD which emits the same signal as the pattern dictionary PTD output and memorizes it in memorizing region in MPM. This operation is made possible because the dictionary term presently dealt with and corresponds to coincident pattern still exists at the instance of completion pulse. To make above reading-in possible, information must take the shape in which the information which should be memorized in each memorizing region in MPM, namely pattern memorizing region MPR, extraction indication memorizing region MER and production rule memorizing region PRT, exists following the registered term written in Eq.(28). As pattern memorizing part MPM can be realized by simple RAM (random access memory), the structure and operation of this part will not be explained here.
Above is the expression for the case of the successful comparison and the situation when the comparison fails, will be treated now. When, at the duration of state S.sub.C, the condition that output of terminal PA1 and that of PB1 are not the same and output of PA1 terminal is not A.sub.o, the system decides that the piling up comparison has failed and brings the state back to S.sub.A. Simultaneously the measures are taken in which the dictionary scanning information occurs at dictionary scanning information output terminal DST indicating to stop emitting presently generated term and to emit next term and operation of reading-in of next term from pattern dictionary PTD and re-reading-in of tree structure to be compared from tree structure memorizing part IET is done. Doing above-mentioned operation this part PPD re-starts its operation. When fail of comparison by piling up is found after the comparison for all terms in dictionary, state transition signal C.sub.A0 occurs through the effect of the special term in pattern dictionary PTD, with letter "z" in all its constituting columns, and z detector group ZDG and AND circuit following it. As a result, the state is transferred from state S.sub.A which is state of preparation for re-start to state S.sub.0 and simultaneously help signal requesting for intervention of operating man is generated at help signal output terminal HLT.
Above is the explanation for composition and operation of partial pattern finding part PPD. PPD sends coincident pattern and accompanying extraction indication and production rule to pattern memorizing part MPM when comparison is successfully made and sends help signal requesting intervention by human hand, when comparison fails. Comments under each letter in Eq. (27) and (28) express the states of this system when corresponding letters are appearing at PA1 and PB1 respectively. For the case when the same state is repeatedly taken, the number of repetitions is indicated by numbers in circles. It will be found from these equations that state S.sub.D is the state for exception of large parenthesis and its contents from piling up operation and state S.sub.E is the state for arbitrarization symbol A.sub.o.
Next, composition method by electronic circuit and operation of extraction generating part EXG is treated. This part somewhat resembles partial pattern finding part PPD but is a little complicated. FIGS. 76 and 77 show its composition. As the structure is complicated, it is expressed by two figures.
The input terminals receiving signals from outer circuits situated at this part are clock input terminal ECL, tree structure input terminal EXT receiving signal from tree structure memorizing part IET, extraction indication input terminal EXX and start pulse input terminal EST receiving start pulse of this part which is also completion pulse of partial pattern finding part PPD. The output terminals of this part are completion pulse output terminal ECP generating completion pulse which shows that operation in this part has completed, output terminal EXP which generates the output of this part EXG to output deciding part SDS, next information requesting output terminal EXS which sends signal, to extraction indication memorizing region, for the purpose of requesting next information requesting signal to request information next to the one being generated. Extraction indication memorizing region MER mentioned before as realized by RAM (random access memory) is composed by shift-register-like circuit which is clocked by one stage at the arrival of next information requesting signal and sends extraction indication information next to the presently generated one.
As the figure for this part is divided in two parts, connecting terminals between FIG. 76 and FIG. 77 is introduced. EYA, EYB, EYC, EYD, EYE, EYF, EYH, EYI, EYJ, EYK, EYL and EYM generate 1 when extraction generating part EXG takes the states of S.sub.A, S.sub.B, S.sub.C, S.sub.D, S.sub.E, S.sub.F, S.sub.H, S.sub.I, S.sub.J, S.sub.K, S.sub.L and S.sub.M respectively and 0 otherwise. Among above terminals for respective states, EYA, for example, is called A state connecting terminal. EAS and ECR are parts at which pulse is generated when operation for single extraction indication ends. EAS, among them, is no coincidence connecting terminal which generates no coincidence pulse when comparison fails and ECR, among them, is coincidence connecting terminal which generates coincidence pulse when comparison succeeds. EYS and EYZ are space state connecting terminal and z state connecting terminal respectively and transmit information that all stages in A shift register EXA (described later) are memorizing space and that all stages in B shift register EXB (described later) are memorizing z respectively. EA1 and EA2 are first and second A shift register connecting terminals dealing with signals from first and second output terminal of A shift register EXA respectively. Similarly EB1, EB2, EB3 are similar connecting terminals concerning B shift register and, for example, EB1 is first B register connecting terminal. In FIG. 76 EXA is A shift register and memorizes extraction indication information. EXB is B shift register and memorizes output signal from tree structure memorizing part IET. EXC is C shift register memorizing extraction indication information to be sent outside. A shift register EXA has single input terminals which are clock terminal EAL, first and second output terminals EA1 and EA2, except for the measures for simultaneous reading-in.