Publication Details

Regular Paths in Derivation Trees of Context-free Grammars

KOUTNÝ, J. Regular Paths in Derivation Trees of Context-free Grammars. Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4. Brno: Brno University of Technology, 2009. p. 410-414. ISBN: 978-80-214-3870-5.
Czech title
Regulární cesty v derivačních stromech bezkontextových gramatik
Type
conference paper
Language
English
Authors
Koutný Jiří, Ing., Ph.D.
URL
Keywords

regular expression, context-free grammar, path controlled grammar, derivation tree, rule tree

Abstract

To increase the generative capacity of context-free grammars, Čulik and Maurer have published an idea of regular restricting the levels in the derivation trees of CF grammars. A simple and natural question is what happens if we put the same request not on the levels, but on the paths of derivation trees of CF grammars. In contrast with regular restricting the levels, regular restricting the paths does not increase the generative capacity of CF grammars. This paper formulates a formal proof.

Published
2009
Pages
410–414
Proceedings
Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4
Conference
Student EEICT 2009, FEKT VUT v Brně, CZ
ISBN
978-80-214-3870-5
Publisher
Brno University of Technology
Place
Brno
BibTeX 
@inproceedings{BUT91220,
  author="Jiří {Koutný}",
  title="Regular Paths in Derivation Trees of Context-free Grammars",
  booktitle="Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4",
  year="2009",
  pages="410--414",
  publisher="Brno University of Technology",
  address="Brno",
  isbn="978-80-214-3870-5",
  url="http://www.feec.vutbr.cz/EEICT/2009/sbornik/03-Doktorske%20projekty/07-Informacni%20systemy/07-xkoutn11.pdf"
}
Back to top