Publication Details

On the Nonterminal Complexity of Left Random Context E0L Grammars

ZEMEK, P. On the Nonterminal Complexity of Left Random Context E0L Grammars. Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011. p. 510-514. ISBN: 978-80-214-4273-3.
Czech title
O neterminální složitosti levých E0L gramatik s nahodilým kontextem
Type
conference paper
Language
English
Authors
Zemek Petr, Ing., Ph.D.
URL
Keywords

Formal languages, left random context E0L grammars, nonterminal complexity

Abstract

The present paper studies the nonterminal complexity of left random context E0L grammars. More specifically, it proves that every recursively enumerable language can be generated by a left random context E0L grammar with nine nonterminals. In the conclusion, some open problems related to the achieved result are stated.

Published
2011
Pages
510–514
Proceedings
Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3
ISBN
978-80-214-4273-3
Publisher
Faculty of Information Technology BUT
Place
Brno
BibTeX 
@inproceedings{BUT91268,
  author="Petr {Zemek}",
  title="On the Nonterminal Complexity of Left Random Context E0L Grammars",
  booktitle="Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3",
  year="2011",
  pages="510--514",
  publisher="Faculty of Information Technology BUT",
  address="Brno",
  isbn="978-80-214-4273-3",
  url="http://www.feec.vutbr.cz/EEICT/2011/sbornik/03-Doktorske%20projekty/08-Informacni%20systemy/11-xzemek02.pdf"
}
Back to top