Computing \(\textit{pre}^{*}\) for General Context Free Grammars

A systematic approach for addressing various problems related to context-free grammars involves employing the \({ pre}^*\) -method. This method calculates, for a given regular language L (given as an NFA), the language of all strings \(\alpha \) (represented by an NFA) for which there exists a \(\beta \in L\) such that \(\alpha {\mathop {\Rightarrow }\limits ^{*}}\beta \) . The range of admissible problems encompasses, inter alia, the word problem, the emptiness problem, the finiteness problem, and the identification of useless symbols. Efficient algorithms have been developed to compute \({ pre}^*(L)\) , but they assume that the grammar adheres to a restricted normal form. In this context, we introduce a novel algorithm that is both straightforward and efficient, while working with general context-free grammars. In addition to the computation of \({ pre}^*\) , this algorithm proves valuable for the construction of parse trees. The running time is in general cubic, but quadratic for parsing unambiguous context-free languages. We provide some evidence suggesting the running times cannot be improved significantly with current techniques.