Publication Details

Regular Paths in Derivation Trees of Context-free Grammars

KOUTNÝ Jiří. Regular Paths in Derivation Trees of Context-free Grammars. In: Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4. Brno: Brno University of Technology, 2009, pp. 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. (DIFS FIT BUT)
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, Brno, CZ
ISBN
978-80-214-3870-5
Publisher
Brno University of Technology
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8924,
   author = "Ji\v{r}\'{i} Koutn\'{y}",
   title = "Regular Paths in Derivation Trees of Context-free Grammars",
   pages = "410--414",
   booktitle = "Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4",
   year = 2009,
   location = "Brno, CZ",
   publisher = "Brno University of Technology",
   ISBN = "978-80-214-3870-5",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8924"
}
Back to top