Publication Details

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

BIDLO Radek and BLATNÝ Petr. How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals. In: Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3. Brno: Faculty of Electrical Engineering and Communication BUT, 2005, pp. 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. (DIFS FIT BUT)
Blatný Petr, Ing. (DIFS FIT BUT)
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, CZ
BibTeX
@INPROCEEDINGS{FITPUB7772,
   author = "Radek Bidlo and Petr Blatn\'{y}",
   title = "How to Generate Recursively Enumerable Languages Using Only Context-free Productions and Eight Nonterminals",
   pages = "536--541",
   booktitle = "Proceedings of 11th Conference and Competition Student EEICT 2005, Volume 3",
   year = 2005,
   location = "Brno, CZ",
   publisher = "Faculty of Electrical Engineering and Communication BUT",
   ISBN = "80-214-2890-2",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/7772"
}
Back to top