Publication Details

On the Nonterminal Complexity of Left Random Context E0L Grammars

ZEMEK Petr. On the Nonterminal Complexity of Left Random Context E0L Grammars. In: Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3. Brno: Faculty of Information Technology BUT, 2011, pp. 510-514. ISBN 978-80-214-4273-3. Available from: http://www.feec.vutbr.cz/EEICT/2011/sbornik/03-Doktorske%20projekty/08-Informacni%20systemy/11-xzemek02.pdf
Czech title
O neterminální složitosti levých E0L gramatik s nahodilým kontextem
Type
conference paper
Language
english
Authors
Zemek Petr, Ing. (DIFS FIT BUT)
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
Conference
Student EEICT 2011, Brno, CZ
ISBN
978-80-214-4273-3
Publisher
Faculty of Information Technology BUT
Place
Brno, CZ
BibTeX 
@INPROCEEDINGS{FITPUB9593,
   author = "Petr Zemek",
   title = "On the Nonterminal Complexity of Left Random Context E0L Grammars",
   pages = "510--514",
   booktitle = "Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3",
   year = 2011,
   location = "Brno, CZ",
   publisher = "Faculty of Information Technology BUT",
   ISBN = "978-80-214-4273-3",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9593"
}
Back to top