Faculty of Information Technology, BUT

Publication Details

Workspace Theorems for Regular-Controlled Grammars

MEDUNA Alexander and ZEMEK Petr. Workspace Theorems for Regular-Controlled Grammars. Theoretical Computer Science, vol. 412, no. 35, pp. 4604-4612. ISSN 0304-3975. Available from: http://www.sciencedirect.com/science/article/pii/S0304397511003513
Czech title
Workspace věty pro gramatiky řízené regulárním jazykem
Type
journal article
Language
english
Authors
URL
Keywords
Regular-controlled context-free grammars, workspace theorems, removal of erasing rules
Abstract
This paper establishes a workspace theorem in terms of regular-controlled (context-free) grammars. It proves that, if, for a regular-controlled grammar H, there is a positive integer k such that H generates every sentence y in L(H) by a derivation in which every sentential form x contains at most (k-1)|x|/k occurrences of nonterminals that are erased throughout the rest of the derivation, where |x| denotes the length of x, then the language of H is generated by a propagating regular-controlled grammar. An analogical workspace theorem is demonstrated for regular-controlled grammars with appearance checking. The paper provides an algorithm that removes all erasing rules from any regular-controlled grammar (possibly with appearance checking) that satisfies the workspace condition above without affecting the generated language. In its conclusion, the paper points out a relationship of the workspace theorems to other areas of formal language theory.
Published
2011
Pages
4604-4612
Journal
Theoretical Computer Science, vol. 412, no. 35, ISSN 0304-3975
Publisher
Elsevier Science
DOI
BibTeX
@ARTICLE{FITPUB9583,
   author = "Alexander Meduna and Petr Zemek",
   title = "Workspace Theorems for Regular-Controlled Grammars",
   pages = "4604--4612",
   journal = "Theoretical Computer Science",
   volume = 412,
   number = 35,
   year = 2011,
   ISSN = "0304-3975",
   doi = "10.1016/j.tcs.2011.04.042",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9583"
}
Back to top