Detail výsledku

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.
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Koutný Jiří, Ing., Ph.D., UIFS (FIT)
Abstrakt

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.

Klíčová slova

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

URL
Rok
2009
Strany
410–414
Sborník
Proceedings of the 15th Conference STUDENT EEICT 2009 Volume 4
Konference
Student EEICT 2009
ISBN
978-80-214-3870-5
Vydavatel
Brno University of Technology
Místo
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"
}
Výzkumné skupiny
Výzkumná skupina formálních modelů (VZ FM)
Pracoviště
Ústav informačních systémů (UIFS)
Nahoru