Journal Articles
| Meduna, A., Zemek, P.: Workspace Theorems for Regular-Controlled Grammars, In: Theoretical Computer Science, Vol. 412, No. 35, 2011, Paris, FR, p. 4604-4612, ISSN 0304-3975 | | Publication language: | english |
|---|
| Original title: | Workspace Theorems for Regular-Controlled Grammars |
|---|
| Title (cs): | Workspace věty pro gramatiky řízené regulárním jazykem |
|---|
| Pages: | 4604-4612 |
|---|
| Place: | FR |
|---|
| Year: | 2011 |
|---|
| URL: | http://www.sciencedirect.com/science/article/pii/S0304397511003513 |
|---|
| Journal: | Theoretical Computer Science, Vol. 412, No. 35, Paris, FR |
|---|
| ISSN: | 0304-3975 |
|---|
| URL: | http://www.sciencedirect.com/science/article/pii/S0304397511003513 [HTML] |
|---|
| Keywords |
|---|
| Regular-controlled context-free grammars, workspace theorems, removal of erasing rules |
| Annotation |
|---|
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.
|
| BibTeX: |
|---|
@ARTICLE{
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},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=9583}
} |
|
Faculty of Information Technology
![[dnssec]](/common/img/dnssec.png)