HEURISTIC DERIVATION SEEKER FOR UNIFORM PREFIX LANGUAGES

摘要

This paper describes the theoretical background and the realization of a program which tries to find the derivation of a prefix word ('the problem) for some classes of uniform prefix languages.nThe program can be applied to different language specifications which may contain a base alphabet, defined symbols, axioms, a sub¬stitution rule and transformation rules. The specification is similar to formalized logic, but is capable of expressing a much broader class of languages. The program reduces the problem to a Syntactic Normal Form and tries to find its derivation from the ad hoc productions of the language by using a heuristic goal-subgoal method (i.e. , one which does not guarantee success, but usually results in better performance).nThe paper also contains a proof that it is sufficient to work with the Normal Form instead of the original problem.