Publication Details

How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals

BIDLO, R.; BLATNÝ, P. How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals. Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3. Brno: Faculty of Electrical Engineering and Communication BUT, 2005. p. 536-541. ISBN: 80-214-2890-2.

Czech title

Jak generovat rekurzívně vyčíslitelné jazyky použitím pouze bezkontextových pravidel a osmi nonterminálů

Type

conference paper

Language

English

Authors

Bidlo Radek, Ing., Ph.D.
Blatný Petr, Ing., Ph.D.

Keywords

Context-Free Grammars, Derivations, Free Groups, Recursively Enumerable Languages

Abstract

The notion of a context-free grammar over a free group is introduced. The transformation of any type-0 grammar to an equivalent context-free grammar over a free group is demonstrated. This approach causes an undesirable increase of the number of nonterminal symbols. Hence we introduce a method for their reduction.

Published

2005

Pages

536–541

Proceedings

Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3

Conference

STUDENT EEICT 2005, Brno, CZ

ISBN

80-214-2890-2

Publisher

Faculty of Electrical Engineering and Communication BUT

Place

Brno

BibTeX

@inproceedings{BUT18908,
  author="Radek {Bidlo} and Petr {Blatný}",
  title="How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals",
  booktitle="Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3",
  year="2005",
  pages="536--541",
  publisher="Faculty of Electrical Engineering and Communication BUT",
  address="Brno",
  isbn="80-214-2890-2"
}