Result Details

A New Normal Form for Programmed Grammars

VRÁBEL, L. A New Normal Form for Programmed Grammars. Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011. p. 500-504. ISBN: 978-80-214-4273-3.
Type
conference paper
Language
English
Authors
Vrábel Lukáš, Ing., DIFS (FIT)
Abstract

In the present paper, we discuss programmed grammars. We investigate the effect of the number of rules with more than one successor on generative power of the programmed grammars. We prove that for every programmed grammar, there is an equivalent programmed grammar where only a single rule has more than one successor.

Keywords

Programmed grammar, complexity, normal form, successor

Published
2011
Pages
500–504
Proceedings
Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3
Conference
Student EEICT 2011
ISBN
978-80-214-4273-3
Publisher
Faculty of Information Technology BUT
Place
Brno
BibTeX 
@inproceedings{BUT91269,
  author="Lukáš {Vrábel}",
  title="A New Normal Form for Programmed Grammars",
  booktitle="Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3",
  year="2011",
  pages="500--504",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="978-80-214-4273-3"
}
Projects
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Formal Model Research Group (RG FM)
Departments
Department of Information Systems (DIFS)
Back to top