Result Details
k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars
ZEMEK, P. k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars. Proceedings of the 16th Conference and Competition STUDENT EEICT 2010. Volume 3. Brno: Faculty of Information Technology BUT, 2010. p. 42-44. ISBN: 978-80-214-4078-4.
Type
conference paper
Language
English
Authors
Zemek Petr, Ing., Ph.D.
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.
Keywords
regular-controlled context-free grammar, removal of erasing rules
URL
Published
2010
Pages
42–44
Proceedings
Proceedings of the 16th Conference and Competition STUDENT EEICT 2010
Series
Volume 3
Conference
Student EEICT 2010
ISBN
978-80-214-4078-4
Publisher
Faculty of Information Technology BUT
Place
Brno
BibTeX
@inproceedings{BUT91250,
author="Petr {Zemek}",
title="k-Limited Erasing Performed by Regular-Controlled Context-Free Grammars",
booktitle="Proceedings of the 16th Conference and Competition STUDENT EEICT 2010",
year="2010",
series="Volume 3",
pages="42--44",
publisher="Faculty of Information Technology BUT",
address="Brno",
isbn="978-80-214-4078-4",
url="http://www.feec.vutbr.cz/EEICT/2010/sbornik/02-Magisterske_projekty/07-Informacni_systemy/11-xzemek02.pdf"
}
Research groups
Formal Model Research Group (RG FM)
Departments