Thinning Context-free Languages

Résumé du livre

When $\delta$ may include non-terminals the problem is more difficult to formalize: we'll define a language $L_{\delta}(G)$ formed by carrying out a thinning procedure on each parse tree generated by $G$. This yields an extension of the fully-terminal problem which is unsolved and seems very hard. An easier problem follows from defining a language $L_{\Delta}(G)$ formed by thinning the parse trees of $G$ with respect to a set of thinning-tree examples instead of a single thinning-string example. We will develop an effective procedure for generating a grammar $H$ for which $L(H)$ = $L_{\Delta}$$(G)$. By choosing an appropriate thinning set $\Delta$, we can use this method to get an approximate solution to the general problem.