Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Thinning Context-Free Languages

Thinning Context-Free Languages

File(s)
92-1318.ps (338.21 KB)
92-1318.pdf (1.29 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6240
Collections
Computer Science Technical Reports
Author
Webber, Adam Brooks
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.

Date Issued
1992-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR92-1318
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance