Belgorod, Belgorod, Russian Federation
The article considers the problem of reducing the number of states of the pushdown recognizer by eliminating unnecessary transitions that never work, and eliminating unnecessary states in which cannot be recognizer in processing a valid chain. There are suggested a search algorithm of unnecessary transitions and states, based on the representation of recognizer as a graph. The article demonstrates the example of recognizer in which the proposed algorithm eliminates unnecessary transitions and states. This algorithm does not guarantee elimination of all unnecessary transitions and states. The article demonstrates the example of recognizer with unnecessary transitions and states that are not detected by the algorithm. The proposed algorithm can be used at software design the processing for formal languages.
context-free language, pushdown recognizer, state, transition, equivalent transforming.
1. Schutzenberger M.P. “On context-free languages and pushdown automata”, Information and Control 6:3 (1963), pp. 246 - 264.
2. Akho A., Ul´man Dzh. Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii. M.: Mir, 1978. T. 1. 612 s.
3. L´yuis F., Rozenkrants D., Stirnz R. Teoreticheskie osnovy proektirovaniya kompilyatorov. M.: Mir, 1979. 656 s.
4. Martynenko B.K. Sintaksicheski uprav-lyaemaya obrabotka dannykh. Izd. 2-e, dopoln. SPb: Izd-vo S.-Peterburgskogo universiteta, 2004 g. 317 s.
5. Akho A, Lam M., Seti R., Ul´man Dzh. Kompilyatory. Printsipy, tekhnologii i in-strumentariy. M: Izdatel´skiy dom “Vil´yams”, 2008. 1185 s.
6. Hopcroft J.E., Motwani R., J.D. Ullman J.D. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson., 2013. p. 496.
7. Belousov A.I., Tkachev S.B. Mul´tigra-fovoe predstavlenie avtomatov s magazinnoy pamyat´yu. Nauka i obrazovanie: nauchnoe izdanie MGTU im. N.E. Baumana. 2012. № 9. S. 11.
8. Stanevichene L.I. Grafy magazinnykh avtomatov. Uchreditel´naya konf. Rossiyskoy assotsiatsii "Zhenshchiny-matematiki". Tez. dokl. M. 1993(a). S. 50
9. Vylitok A.A. O postroenii grafa magazinnogo avtomata. Vestn. Mosk. un-ta. Ser. 15. 1996. № 3. S. 68 - 73.
10. Brauer V. Vvedenie v teoriyu konechnykh avtomatov M.: Kniga po Trebovaniyu, 2012. S. 272.
11. Ryazanov Yu. D. Sintez raspoznavateley s magazinnoy pamyat´yu po determinirovannym sintaksicheskim diagrammam. Vestnik VGU. Sistemnyy analiz i informatsionnye tekhnologii. 2014. №1. S. 138-145.
12. Ryazanov Yu. D., Savelova I. N. Preobrazovanie raspoznavatelya s magazinnoy pamyat´yu i odnim sostoyaniem v raspoznavatel´ s konechnym mnozhestvom sostoyaniy. Modelirovanie, optimizatsiya i informatsionnye tekhnologii. 2015. № 4 (11). S. 13.
13. Polyakov V.M., Ryazanov Y.D. Virt Charts to Multiport Component Syntactic Charts Transformation. Global Journal of Pure and Applied Mathematics. 2015. T. 11. № 5. S. 3939-3952.
