Описывается метод генерации тестов минимальной длины для синтаксически управляемых конечных процессоров, реализующих регулярные языки. Критерий выбора тестовых вариантов выражает заданную степень покрытия дуг графа, представляющего регулярное выражение, по которому строится процессор. Поскольку дуги графа помечены семантическими метками, то критерий выражает соответствующую степень взаимодействия между семантиками, и тест гарантирует выполнение этого критерия. Метод основан на алгоритме решения задачи Китайского почтальона на ориентированном графе, выводимом из регулярного выражения, определяющем конечно-автоматный язык, реализуемом процессором. С. 17-45

A method of generation of tests of minimum length for the purpose of testing of syntax directed finite processors recognizing regular languages is described. A criterion of the test cases selection is introduced that represents the requested level of coverage for the acres of the graph that corresponds to the regular expression for which the processor has been constructed. Since the graph acres are labeled with semantic labels, the criterion defines the degree of interaction between these semantics, so such a test must be built that the criterion conditions are met. The method is based on the algorithm of the solution of the Chinese Postman Problem on a directed graph, that is built for the input regular expression that defines the language recognized by the finite processor.