# Determining when a substring has a unique parse forest

Given an arbitrary (potentially ambiguous) context free grammar $$G: \mathbb{G}$$, and string $$\alpha: \Sigma^\ast$$, is there a decision procedure that returns whether appending and/or prepending symbols can alter the parse forest of $$\alpha$$? In other words, we want a function $$F: (\mathbb{G} \times \Sigma^\ast) \rightarrow \mathbb{B}$$ that returns whether $$\alpha$$'s parse forest according to $$G$$ is unique over $$\beta\alpha\gamma$$, for all $$\beta, \gamma: \Sigma^\ast$$.

Specifically, let $$T_\alpha$$ denote the set of all parse trees that are generated by the string $$\alpha$$ using $$G$$, and consider $$\mathbf{T}_{\alpha}$$, the union of all parse trees and their subtrees that (1) can be generated by $$\beta\alpha\gamma$$ using $$G$$ for arbitrary $$\beta, \gamma \in \Sigma^\ast$$, and (2) have a leaf in $$\alpha$$. The parse forest $$T_\alpha$$ is unique iff $$\forall t \in \mathbf{T}_{\alpha}\exists t' \in T_\alpha$$, such that $$t$$ is either a subtree of $$t'$$, or $$t'$$ is a proper subtree of $$t$$.

Some context: effectively, we want the necessary and sufficient conditions for when a substring can be replaced by a single nonterminal (or set of nonterminals, in the case of ambiguity) without affecting parse trees of surrounding or adjacent strings.