TRANSFORMING OF THE PUSHDOWN RECOGNIZER WITH ONE STATE INTO RECOGNIZER WITH FINITE SET OF STATES
UDC 519.685.3
DOI:
In this paper, we define the class of pushdown recognizers with one state which can be transformed to equivalent pushdown recognizers with finite set of states and the algorithm of transformation. Recognizer with a finite set of states performing fewer operations over the pushdown memory than equivalent recognizer with one state
1. Lewis F., Rosencrantz D., Stearns R. Theoretical Foundations compiler design. - M.: Mir, 1979.- 656 p.
2. Aho A., Ulman J. Theory of parsing, translation and compilation. - M .: Mir, 1978.- t. 1, 612 s., - t. 2, 487 s.
3. Ryazanov Yu. D. Synthesis of recognizers with store memory by deterministic syntactic diagrams // Bulletin of the Voronezh State University. System analysis and information technology. 2014. No1. with. 138 - 145.
Keywords: context-free language, pushdown recognizer, state, equivalent transforming
For citation: Ryazanov Y.D., Savelova I.N. TRANSFORMING OF THE PUSHDOWN RECOGNIZER WITH ONE STATE INTO RECOGNIZER WITH FINITE SET OF STATES. Modeling, Optimization and Information Technology. 2015;3(4). URL: https://moit.vivt.ru/wp-content/uploads/2015/12/RyazanovSavelova_4_15_1.pdf DOI: (In Russ).
Published 31.12.2015