Detail publikačního výsledku

On the Nonterminal Complexity of Left Random Context E0L Grammars

ZEMEK, P.

Original Title

On the Nonterminal Complexity of Left Random Context E0L Grammars

English Title

On the Nonterminal Complexity of Left Random Context E0L Grammars

Type

Paper in proceedings outside WoS and Scopus

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.

English 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

Key words in English

Formal languages, left random context E0L grammars, nonterminal complexity

Authors

ZEMEK, P.

Released

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

Full text in the Digital Library

http://hdl.handle.net/

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