Publication Details

k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars

ZEMEK Petr. k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars. In: Proceedings of the 16th Conference and Competition STUDENT EEICT 2010. Volume 3. Brno: Faculty of Information Technology BUT, 2010, pp. 42-44. ISBN 978-80-214-4078-4.
Czech title
k-limitované vymazávání prováděné bezkontextovými gramatikami řízenými regulárním jazykem
Type
conference paper
Language
english
Authors
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords

regular-controlled context-free grammar, removal of erasing rules

Abstract

A regular-controlled context-free grammar erases its nonterminals in a k-limited way, where k >= 0, if in every sentential form x of any successful derivation x contains at most k|x|/(k+1) nonterminals from which it does derive the empty string, where |x| is the length of x. This paper demonstrates that any regular-controlled context-free grammar that erases its nonterminals in this way can be converted to an equivalent regular-controlled context-free grammar without any erasing rules, while it is not known whether this is possible in general.

Published
2010
Pages
42-44
Proceedings
Proceedings of the 16th Conference and Competition STUDENT EEICT 2010
Series
Volume 3
Conference
Student EEICT 2010, Brno, CZ
ISBN
978-80-214-4078-4
Publisher
Faculty of Information Technology BUT
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB9259,
   author = "Petr Zemek",
   title = "k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars",
   pages = "42--44",
   booktitle = "Proceedings of the 16th Conference and Competition STUDENT EEICT 2010",
   series = "Volume 3",
   year = 2010,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "978-80-214-4078-4",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9259"
}
Back to top