Publication 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.
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., Ph.D.
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, FEKT VUT v Brně, CZ
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"
}
Back to top