Thinning Context-Free Languages

Abstract

A thinning is a kind of transformation suggested by a practical problem in program optimization. We're given a thinning example $\delta$, which is a string with one or more symbols marked. To thin a language with respect to this $\delta$ is to edit each word to reflect the observation that the marked symbols of $\delta$ are unnecessary and should be omitted. In this paper we'll explore thinnings of context-free languages. When $\delta$ is a fully-terminal string we'll define a language $L_{\delta} (G)$ formed by carrying out a thinning procedure on each word in $L(G)$. For a large class of thinning examples--the class for which the language of strings correctly marked for thinning is regular--we will demonstrate that $L_{\delta}(G)$ is a context-free language and that there is an effective procedure for generating a grammar $H$ for which $L(H)$ = $L_{\delta}(G)$. 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.