Delimitação da expressividade do operador pushdown: restrições estruturais para a construção de autômatos de pilha determinísticos

Abstract

Context-free expressions extended with the Pushdown Operator (PDOp) form a denotati- onal formalism capable of representing the entire class of context-free languages. However,

the existing algorithm for converting such expressions into pushdown automata typically yields nondeterministic models whose execution is inefficient on deterministic machines and may exhibit undesirable behaviors, such as infinite computational cycles triggered by the presence of the empty word. This work investigates formal and structural restrictions that enable the construction of deterministic pushdown automata (DPDAs) from PDOp expressions, with an initial focus on the operator’s base case. The methodology combines a theoretical–formal approach with controlled computational experimentation, involving the analysis of existing algorithms, the identification of sources of nondeterminism, the definition of structural criteria for eliminating unproductive recursions, and the proposal

of a new algorithmic architecture. As its main contribution, the study introduces a linea- rized conversion process and a heuristic pipeline for reducing structural nondeterminism,

thereby making the PDOp more suitable for deterministic computational environments. The results indicate that the proposed approach represents a significant step toward the

development of a PDOp-based expression compiler capable of generating correct and ef- ficient DPDAs.