Publication detail

On the Nonterminal Complexity of Left Random Context E0L Grammars

ZEMEK, P.

Original Title

On the Nonterminal Complexity of Left Random Context E0L Grammars

Type

article in a collection out of WoS and Scopus

Language

English

Original 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.

Keywords

Formal languages, left random context E0L grammars, nonterminal complexity

Authors

ZEMEK, P.

Released

28. 4. 2011

Publisher

Faculty of Information Technology BUT

Location

Brno

ISBN

978-80-214-4273-3

Book

Proceedings of the 17th Conference STUDENT EEICT 2011 Volume 3

Pages from

510

Pages to

514

Pages count

5

URL

http://www.feec.vutbr.cz/EEICT/2011/sbornik/03-Doktorske%20projekty/08-Informacni%20systemy/11-xzemek02.pdf

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"
}