TRANSFORMING OF THE PUSHDOWN RECOGNIZER WITH ONE STATE INTO RECOGNIZER WITH FINITE SET OF STATES

UDC 519.685.3

Y.D. Ryazanov, I.N. Savelova

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.

Keywords: context-free language, pushdown recognizer, state, equivalent transforming.

Full text:
RyazanovSavelova_4_15_1.pdf