登入選單

返回Google圖書搜尋

Thinning Context-free Languages

Cornell University. Department of Computer ScienceAdam Brooks Webber

出版	Cornell University, Department of Computer Science, 1992
URL	http://books.google.com.hk/books?id=2p1gHAAACAAJ&hl=&source=gbs_api

註釋

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.