Syntax Directed Generation of Tests for Processors of Regular Languages
Abstract
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.
References
[2] B. Martynenko, “Towards the 80th Anniversary of N. Wirth: Wirth’s Syntactic Charts in the SYNTAXTechnology,” in 3rd International Conference on Computer Technology in Russia and in the Former Soviet (SoRuCom 2014), Kazan, Russia, 13-17 Oct. 2014, pp. 199–206; doi: 10.1109/SoRuCom.2014.52
[3] B. K. Martynenko, Sintaksicheski upravlyaemaya obrabotka dannykh [Syntactically managed data processing]. 2nd ed., Saint-Petersburg, Russia: SPbSU, 2004 (in Russian).
[4] J. R. Evanas and E. Minieka, Optimization Algorithms for Networks and Graphs, 2nd ed., New York, NY, USA: Marcel Dekker, 1992.
[5] J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata, Reading, MA: Addison Wesley, 1969.
[6] A. P. Ershova, S. S. Lavrova, and M.R. Shura-Bura eds., Algoritmicheskii yazyk Algol-60. Peresmotrennoe soobshchenie. [Revised Report on the Algorithmic Language Algol 60], Moscow, USSR: Mir, 1965 (in Russian).
[7] F. Harary, R. Z. Norman, and D. Cartwright, Structural Models: An Introduction to the Theory of Directed Graphs, Wiley, 1966.
This work is licensed under a Creative Commons Attribution 4.0 International License.
